Pasionat de informatică şi de puzzle-uri, Dorel a construit o matrice $A$ de dimensiunea $N×M$ lipind mai multe piese dreptunghiulare de diferite dimensiuni. Fiecare piesă este compusă din elemente de dimensiunea $1×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≤x1≤x2≤N, 1≤y1≤y2≤M)$ , unde creşte toate valorile elementelor submatricei cu valoarea $V$.

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≤x1≤x2≤N, 1≤y1≤y2≤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ă.

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ă.

h2. Cerinţe

h2. 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 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

● 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 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

h2. Date de ieşire