- Time limit: 1.00 s
- Memory limit: 128 MB
Lisäksi sinulle on annettu joukko kyselyitä. Jokainen kysely koskee tiettyä suorakulmion muotoista aluetta metsässä, ja tehtäväsi on ilmoittaa puiden määrä alueella.
Syöte
Syötteen ensimmäisellä rivillä on kolme kokonaislukua $n$, $m$ ja $q$. Tämä tarkoittaa, että metsän koko on $n \times m$ ruutua ja kyselyiden määrä on $q$.
Tämän jälkeen syötteessä on $n$ riviä, jotka kuvaavat metsän. Jokainen ruutu on tyhjä (
.
) tai puu (*
).Lopuksi syötteessä on $q$ riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on neljä kokonaislukua $y_1$, $x_1$, $y_2$ ja $x_2$, jotka määrittävät kyseltävän alueen.
Tuloste
Ohjelmasi tulee ilmoittaa jokaisesta kyselystä, montako puuta on alueella.
Rajat
- $1 \le n, m \le 1000$
- $1 \le q \le 10^5$
- $1 \le y_1 \le y_2 \le n$
- $1 \le x_1 \le x_2 \le m$
Syöte:
4 7 3
.*...*.
**..*.*
.**.*..
......*
1 1 2 2
3 2 4 7
2 5 2 5
Tuloste:
3
4
1