== include(page="template/taskheader" task_id="lcdr") ==

Poveste şi cerinţă...

Se dă o matrice de dimensiuni $N*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 $L1$ şi $L2$ ale matricei, inclusiv L1 şi L2?

h2. Date de intrare

Fişierul de intrare $lcdr.in$ ...

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$, $L1$, $L2$ cu semnificaţia din enunţ.

h2. Date de ieşire

În fişierul de ieşire $lcdr.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

 1 ≤ N, M ≤ 500
 1 ≤ Q ≤ 500 000
 
 
 
* $1 ≤ N, M ≤ 500$
* $1 ≤ Q ≤ 500 000$
* Pentru 30% din teste, Q ≤ 500
* Pentru alte 40% din teste, Q ≤ 200 000

h2. Exemplu