• 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