Fişierul intrare/ieşire:	matrice3.in, matrice3.out	Sursă	Algoritmiada 2010, Runda 4
Autor	Paul-Dan Baltescu	Adăugată de	Paul-Dan Baltescu •pauldb
Timp execuţie pe test	0.35 sec	Limită de memorie	10240 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Matrice3

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₁ y₁) şi colţul dreapta-jos în (x₂ y₂)?

Cerinţă

Răspundeţi la întrebările Laurei.

Date de intrare

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₁ y₁ x₂ y₂ reprezentând colţurile dreptunghiului din fiecare întrebare.

Date de ieşire

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.

Restricţii

• 1 ≤ N, M ≤ 250
• 1 ≤ Q ≤ 250 000
• 1 ≤ x₁ ≤ x₂ ≤ N
• 1 ≤ y₁ ≤ y₂ ≤ M
• Pentru 30% din teste N, M ≤ 40 şi Q ≤ 250.
• Pentru alte 30% din teste Q ≤ 100 000.

Exemplu

Cum se trimit solutii?