lcdr

Cerință

Se dă o matrice de dimensiuni $N \cdot M$. Toate elementele matricei au valoarea $0$ sau $1$. Vor exista $Q$ întrebări de forma: există vreun dreptunghi cu $L$ linii şi $C$ coloane cu toate elementele egale cu $1$ situat în întregime între liniile $L_1$ şi $L_2$ ale matricei, inclusiv $L_1$ şi $L_2$?

Date de intrare

Fisierul lcdr.in conţine pe prima linie numerele $N$, $M$ şi $Q$ cu semnificaţia din enunţ. Următoarele $N$ linii vor conţine fiecare câte $M$ numere cu valoarea $0$ sau $1$, fără spaţii între ele. Urmează $Q$ linii cu câte patru numere fiecare: $L$, $C$, $L_1$, $L_2$ cu semnificaţia din enunţ.

Date de ieșire

Fişierul lcdr.out va conţine $Q$ numere, câte unul pe linie reprezentând răspunsurile la întrebări.

Restricții și precizări

• $1 \leq N, M \leq 500$
• $1 \leq Q \leq 500 \ 000$
• Pentru $30\%$ din teste, $Q \leq 500$.
• Pentru alte $40\%$ din teste, $Q \leq 200 \ 000$.

Exemplu

lcdr.in

4 5 5
00000
11100
01111
01100
3 2 2 4
4 3 1 4
1 3 1 2
1 2 4 4
1 3 4 4

lcdr.out

1
0
1
1
0