== include(page="template/taskheader" task_id="matrice3") ==
Poveste şi cerinţă...
Laura are o nouă matrice, de data aceasta binară, având $N$ linii şi $M$ coloane. Ca de obicei, curioasă din fire, Laura vă pune $Q$ întrebări de forma: _Care este latura maximă a unui pătrat ce conţine în interior doar $0$ inclus complet în dreptunghiul cu colţul stânga-sus în $(x{~1~} y{~1~})$ şi colţul dreapta-jos în $(x{~2~} y{~2~})$?_
h2. Cerinţă
Răspundeţi la întrebările Laurei.
h2. Date de intrare
Fişierul de intrare $matrice3.in$ ...
Pe prima linie a fişierului de intrare $matrice3.in$ se află $3$ numere întregi $N$, $M$ şi $Q$ cu semnificaţia din enunţ. Pe următoarele $N$ linii se află câte $M$ cifre din mulţimea ${0, 1}$, ce reprezintă matricea Laurei. Următoarele $Q$ linii conţin câte 4 numere $x{~1~} y{~1~} x{~2~} y{~2~}$ reprezentând colţurile dreptunghiului din fiecare întrebare.
h2. Date de ieşire
În fişierul de ieşire $matrice3.out$ ...
Fişierul de ieşire $matrice3.out$ va conţine $Q$ linii, pe i-a linie ({$1 ≤ i ≤ Q$}) se află un singur număr întreg reprezentând răspunsul la a $i$-a întrebare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 250$
* $1 ≤ Q ≤ 250 000$
* $1 ≤ x{~1~} ≤ x{~2~} ≤ N$
* $1 ≤ y{~1~} ≤ y{~2~} ≤ M$
* Pentru $30%$ din teste $N, M ≤ 40$ şi $Q ≤ 250$.
* Pentru alte $30%$ din teste $Q ≤ 100 000$.
h2. Exemplu
table(example). |_. matrice3.in |_. matrice3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 6 4
000101
010100
110001
010001
010000
1 1 3 3
1 1 5 6
2 2 4 5
4 2 5 2
| 1
3
2
0
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="matrice3") ==
