Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Metsä

Metsä


View task | Model solution | Statistics


Metsä

Time limit:1.00 s
Memory limit:128 MB

Sinulle on annettu kuvaus suorakulmion muotoisesta metsästä. Tiedät jokaisesta ruudusta, onko siinä puuta vai ei.

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
Esimerkki

Syöte:
4 7 3
.*...*.
**..*.*
.**.*..
......*
1 1 2 2
3 2 4 7
2 5 2 5


Tuloste:
3
4
1