Sinulle on annettu peikkometsän kartta, johon on merkitty metsässä olevat peikot. Sinulle on myös annettu joukko kyselyitä, joissa täytyy selvittää, onko tietty suorakulmion muotoinen alue peikkometsässä turvallinen. Alue on turvallinen, jos siinä ei ole yhtään peikkoa.

Syöte

Syöteen ensimmäisellä rivillä on kokonaisluvut n ja m: alueen korkeus ja leveys.

Sitten syötteessä on n riviä, joista jokaisella on m merkkiä. Jokainen merkki on . (tyhjä) tai P (peikko).

Seuraavalla rivillä on kokonaisluku q: kyselyiden määrä.

Lopuksi syötteessä on q riviä, joista jokaisella on neljä kokonaislukua y_1, x_1, y_2 ja x_2: kysyttävän alueen ääripisteet.

Tuloste

Ohjelmasi tulee tulostaa, moniko kysytyistä alueista on turvallinen.

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
.....P.
.P....P
....PP.
.......
3
2 3 3 4
3 5 4 7
1 1 1 1

Tuloste:

2