amat

Pasionat de informatică și de puzzle-uri, Dorel a construit o matrice $A$ de dimensiunea $N \times M$ lipind mai multe piese dreptunghiulare de diferite dimensiuni. Fiecare piesă este compusă din elemente de dimensiunea $1 \times 1$ și rețin o aceeași valoare (vezi exemplele). Matricea rezultată nu are spații libere, iar piesele din care este compusă nu se suprapun. Nu există două piese cu aceeași valoare.
Deși inițial părea că acest design este unul inedit, nu a durat mult până când Dorel s-a plictisit. Astfel, acum el dorește să "upgradeze" matricea construită. Dorel alege o submatrice delimitată de coordonatele $(x1,y1)$ - colțul stânga-sus, $(x2,y2)$ - colțul dreapta-jos ($1 \le x1 \le x2 \le N$, $1 \le y1 \le y2 \le M$), unde crește toate valorile elementelor submatricei cu valoarea $V$.

Dorel efectuează în ordine $Q$ operații de upgrade, operații numerotate de la $1$ la $Q$. La finalizarea celor $Q$ operații de upgrade, toate elementele din matrice au valoarea mai mare sau egală cu $K$. După o operație de upgrade, structura inițială a matricei se modifică.

Cerințe

Cum priceperea lui Dorel este proverbială, trebuie să îl ajutați în rezolvarea următoarelor cerințe:

1. determinarea coordonatelor piesei cu număr maxim de elemente înainte ca Dorel să efectueze operațiile de upgrade;
2. determinarea numărului minim de operații de upgrade după care toate elementele matricei au valoarea mai mare sau egală cu $K$.

Date de intrare

Datele de intrare se citesc din fișierul amat.in, care are următoarea structură:

• pe prima linie se află numărul natural $C$, care poate fi egal cu $1$ sau $2$, în funcție de cerința ce trebuie rezolvată;
• pe linia următoare se află două numerele naturale $N$ și $M$ cu semnificația din enunț;
• pe următoarele $N$ linii se găsesc elementele matricei $A$.
• dacă $C=2$ atunci fișierul de intrare mai conține:
  • pe linia $N+2$ numerele naturale $Q$ și $K$ cu semnificațiile din enunț;
  • pe următoarele $Q$ linii descrierea submatricelor asupra cărora se efectuează operații de upgrade de forma: $x1 \ y1 \ x2 \ y2 \ V$.

Date de ieșire

Datele de ieșire se vor scrie în fișierul amat.out, astfel:

Dacă $C=1$ se vor scrie, separate prin spațiu patru numere naturale nenule $x1 \ y1 \ x2 \ y2$ ce reprezintă coordonatele colțului stânga-sus, respectiv colțului dreapta-jos unde este plasată piesa cu număr maxim de elemente înainte de upgrade. Dacă există mai multe astfel de piese, atunci vor fi scrise coordonatele piesei pentru care coordonatele colțului stânga-sus are valoarea liniei cea mai mare, iar la linii egale, se va alege piesa cu coordonata coloanei cea mai mare.

Dacă $C=2$ se va scrie numărul natural nenul $NR$ ce reprezintă numărului minim de operații de upgrade după care toate elementele matricei au valoarea mai mare sau egală cu $K$.

Restricții și precizări

• $2 \le N, M \le 1 \ 000$; $1 \le Q \le 100 \ 000$; $1 \le V \le 1 \ 000$;
• $-1 \ 000 \le$ elementele matricei $A$ înainte de upgrade $\le 1 \ 000$;
• Operațiile de upgrade se efectuează obligatoriu în ordinea citirii;
• Pentru teste în valoare de $30$ de puncte, $C=1$;
• Pentru teste în valoare de $30$ de puncte, $C=2$ și $N, M, Q \le 2 \ 500$;
• Pentru teste în valoare de $50$ de puncte, $C=2$ şi $Q \le 4 \ 000$;
• Pentru teste în valoare de $70$ de puncte, $C=2$.

Exemplul 1

amat.in

1
4 6
1 1 1 3 2 2
1 1 1 3 2 2
6 4 4 4 2 2
6 4 4 4 5 7

amat.out

3 2 4 4

Explicație

Se rezolvă cerința $1$. Matricea inițială construită de Dorel este:

Există $3$ piese cu număr maxim de valori egale, dar piesa care corespunde cerințelor are coordonatele: $3 \ 2 \ 4 \ 4$.

Exemplul 2

amat.in

2
4 6
1 1 1 3 2 2
1 1 1 3 2 2
6 4 4 4 2 2
6 4 4 4 5 7
3 6
1 1 3 3 5
1 2 4 6 5
4 1 4 3 1

amat.out

2

Explicație

Se rezolvă cerința $2$. Matricea inițială construită este cea prezentată mai sus. Dorel efectuează $3$ operații de upgrade.

Matricea obținută după efectuarea primului upgrade:

$\begin{bmatrix} \textcolor{lime}{6} & \textcolor{lime}{6} & \textcolor{lime}{6} & 3 & 2 & 2 \\ \textcolor{lime}{6} & \textcolor{lime}{6} & \textcolor{lime}{6} & 3 & 2 & 2 \\ \textcolor{lime}{11} & \textcolor{lime}{9} & \textcolor{lime}{9} & 4 & 2 & 2 \\ 6 & 4 & 4 & 4 & 5 & 7 \end{bmatrix}$

Matricea obținută după efectuarea celui de-al doilea upgrade:

$\begin{bmatrix} 6 & \textcolor{lime}{11} & \textcolor{lime}{11} & \textcolor{lime}{8} & \textcolor{lime}{7} & \textcolor{lime}{7} \\ 6 & \textcolor{lime}{11} & \textcolor{lime}{11} & \textcolor{lime}{8} & \textcolor{lime}{7} & \textcolor{lime}{7} \\ 11 & \textcolor{lime}{14} & \textcolor{lime}{14} & \textcolor{lime}{9} & \textcolor{lime}{7} & \textcolor{lime}{7} \\ 6 & \textcolor{lime}{9} & \textcolor{lime}{9} & \textcolor{lime}{9} & \textcolor{lime}{10} & \textcolor{lime}{12} \end{bmatrix}$

Matricea obținută după efectuarea celui de-al treilea upgrade:

$\begin{bmatrix} 6 & 11 & 11 & 8 & 7 & 7 \\ 6 & 11 & 11 & 8 & 7 & 7 \\ 11 & 14 & 14 & 9 & 7 & 7 \\ \textcolor{lime}{7} & \textcolor{lime}{10} & \textcolor{lime}{10} & 9 & 10 & 12 \end{bmatrix}$

La final tuturor operațiilor de upgrade, matricea are toate valorile mai mari sau egale cu $6$. Se observă că sunt suficiente primele două operații de upgrade pentru ca toate elementele matricei să fie mai mari sau egale cu $6$.