CSES - 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
  • $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$
Esimerkki

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


Tuloste:
3
4
1