CSES - Peikkometsä
  • Time limit: 4.00 s
  • Memory limit: 128 MB

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 nn ja mm: alueen korkeus ja leveys.

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

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

Lopuksi syötteessä on qq riviä, joista jokaisella on neljä kokonaislukua y1y_1, x1x_1, y2y_2 ja x2x_2: kysyttävän alueen ääripisteet.

Tuloste

Ohjelmasi tulee tulostaa, moniko kysytyistä alueista on turvallinen.

Rajat

  • 1n,m10001 \le n, m \le 1000
  • 1q1051 \le q \le 10^5
  • 1y1y2n1 \le y_1 \le y_2 \le n
  • 1x1x2m1 \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