Lacul

Lacul codrilor albastru
Nuferi galbeni îl încarcă;
Tresărind în cercuri albe
El cutremură o barcă.
Mihai Eminescu, Lacul

Cerință

GrandPaPà, anticul și legendarul păzitor al lacului din poezia Eminesciană "Lacul", a descoperit într-o dimineață $k$ nuferi galbeni patrați pe suprafața apei. Suprafața apei poate fi codificată ca o matrice de $n$ linii si $m$ coloane.

Nufărul cu identificatorul $i$ ($1 \le i \le K$), latura $lat$ și colțurile în regiunile $(l_i,c_i)$, $(l_i,c_i+lat-1)$, $(l_i+lat-1,c_i)$ și $(l_i+lat-1,c_i+lat-1)$ va acoperi toată submatricea corespunzătoare cu valoarea $i$. Se garantează că nu există doi nuferi care să se suprapună, însă doi nuferi se pot atinge pe margini.

Dacă o regiune nu este acoperită de nici un nufăr, atunci elementul aferent din matrice va avea valoarea $0$.

Această problemă are mai multe cerințe. În funcție de numărul cerinței $C$ ($1 \le c \le 3$), va trebui să afișați:

• Dacă $c=1$, afișați $3$ numere, lmax, numar și id — latura maximă a unui nufăr, numărul de nuferi cu latura maximă, respectiv identificatorul minim al unui nufăr cu latura maximă.
• Dacă $c=2$, GrandPaPà va face $Q$ poze la lac, a $i$-a poza cuprinzând submatricea cu colțurile de stânga-sus și dreapta-jos în regiunile $(l_{1_i},c_{1_i})$, respectiv $(l_{2_i},c_{2_i})$. Pentru fiecare poză, afișați numărul de nuferi incluși complet în submatricea fotografiată.
• Dacă $c=3$, similar cu cerința $2$, GrandPaPà va face $Q$ poze la lac. Pentru fiecare poză, afișați numărul de nuferi incluși parțial sau complet în submatricea fotografiată.

Date de intrare

Pe prima linie a fișierului de intrare lacul.in se va afla numărul cerinței $c$ ($1 \le c \le 3$).

Pe a doua linie se vor afla trei numere $n$, $m$ și $k$, ($1 \le n,m \le 100$, $1 \le k \le n \cdot m$) — dimensiunile matricei, respectiv numărul de nuferi.

Pe fiecare dintre următoarele $n$ linii se vor afla câte $m$ numere, elementele matricei ($0 \le a_{i,j} \le k$).

Dacă $c=2$ sau $c=3$, pe a $n+3$-a linie din fișierul de intrare se va afla $q$ ($1 \le q \le 100.000$) — numărul de poze.

Pe următoarele $q$ linii se vor afla coordonatele colțurilor din stânga-sus, respectiv dreapta-jos a pozelor
($1 \le l_1 \le l_2 \le n$, $1 \le c_1 \le c_2 \le m$).

Date de ieșire

Dacă $c=1$, afișați în fișierul de ieșire lacul.out $3$ numere, latura maximă a unui nufăr, numărul de nuferi cu latura maximă, respectiv identificatorul minim al unui nufăr cu latura maximă.

Dacă $c=2$, afișați, pentru fiecare dintre cele $q$ poze din fișierul de intrare, numărul de nuferi incluși complet în submatricea fotografiată.

Dacă $c=3$, afișați, pentru fiecare dintre cele $q$ poze din fișierul de intrare, numărul de nuferi incluși parțial sau complet în submatricea fotografiată.

Restricții și precizări

• Pentru 20 de puncte, $c=1$;
• Pentru 40 de puncte, $c=2$;
• Pentru restul de 40 de puncte, $c=3$.
• Pentru câte 10 puncte la fiecare dintre cerințele $c=2$ și $c=3$, toți nuferii au latura egală cu $1$;
• Pentru câte 20 puncte la fiecare dintre cerințele $c=2$ și $c=3$, $k \le 100$;

Exemplul 1

lacul.in

1
9 10 7
0 0 0 0 1 1 0 0 0 0
2 2 0 0 1 1 7 7 7 7
2 2 0 0 0 0 7 7 7 7
0 4 4 4 3 0 7 7 7 7
0 4 4 4 0 0 7 7 7 7
0 4 4 4 5 5 5 5 6 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0

lacul.out

4 2 5

Explicație

Pentru primul exemplu, există $2$ nuferi cu latura maximă $lmax=4$. Aceștia au identificatoarele $5$, respectiv $7$, dintre care $5$ este cel mai mic.

Exemplul 2

lacul.in

2
9 10 7
0 0 0 0 1 1 0 0 0 0
2 2 0 0 1 1 7 7 7 7
2 2 0 0 0 0 7 7 7 7
0 4 4 4 3 0 7 7 7 7
0 4 4 4 0 0 7 7 7 7
0 4 4 4 5 5 5 5 6 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0
4
1 1 9 10
2 1 5 9
5 4 6 9
1 2 8 8

lacul.out

7
2
1
3

Explicație

Pentru exemplele $2$ și $3$, Cele patru poze suprind următoarele submatrici:

• Toți cei $k=7$ nuferi sunt incluși complet în prima poză.
• Nuferii cu identificatoarele $2$ și $3$ sunt incluși complet în a doua poză.
• Nufărul $6$ este singurul nufăr inclus complet în a treia poză.
• Nuferii $1$, $3$ și $4$ sunt incluși complet în a patra poză.

Exemplul 3

lacul.in

3
9 10 7
0 0 0 0 1 1 0 0 0 0
2 2 0 0 1 1 7 7 7 7
2 2 0 0 0 0 7 7 7 7
0 4 4 4 3 0 7 7 7 7
0 4 4 4 0 0 7 7 7 7
0 4 4 4 5 5 5 5 6 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0
4
1 1 9 10
2 1 5 9
5 4 6 9
1 2 8 8

lacul.out

7
5
4
6

Explicație

• Toți cei $k=7$ nuferi sunt incluși complet în prima poză.
• Nuferii cu identificatoarele $2$ și $3$ sunt incluși complet în a doua poză. Nuferii cu identificatoarele $1$, $4$ și $7$ sunt incluși doar parțial.
• Nufărul $6$ este singurul nufăr inclus complet în a treia poză. Nuferii $4$, $5$ și $7$ sunt incluși doar parțial.
• Nuferii $1$, $3$ și $4$ sunt incluși complet în a patra poză. Nuferii $2$, $5$ și $7$ sunt incluși doar parțial.