LHC

Cercetătorii din cadrul proiectului LHC (Large Hadron Collider) de la Geneva au anunțat descoperirea unei noi forme a materiei: flatquarkon. Aceasta este caracterizată pintr-o structură bidimensională formată din quarci (particule elementare din modelul standard) menținuți în loc prin intermediul forței nucleare tari – similar solidelor ce își capătă proprietățile datorită legăturilor chimice dintre atomii constituenți. Fiecare quark posedă o proprietate numită masă efectivă (denumită mai departe masă), ce include atât masa proprie, cât și efectele produse de interacțiunea cu ceilați quarci. Putem reprezenta masa întregului sistem printr-o matrice cu $N$ linii și $M$ coloane:

unde $m_{ij}$ reprezintă masa quarcului aflat pe linia $i$ și coloana $j$.

Aplicând un câmp magnetic perpendicular pe planul unui flatquarkon, putem activa energetic unul sau mai mulți quarci, aceștia devenind capabili să participe în reacții nucleare. Dacă doi quarci activi sunt adiacenți (se învecinează pe linie sau pe coloană), atunci vor participa împreună în orice reacție nucleară.

Cerința

Considerăm un flatquarkon aflat într-un mediul lipsit de câmpuri magnetice.
Se dă o listă de $Q$ instrucțiuni de două tipuri:

• de tipul $1$: Se aplică un câmp magnetic asupra quarcului de pe linia $i$ și coloana $j$. Dacă quarcul este inactiv, acesta va fi activat de câmpul magnetic. Dacă este deja activ, nu se va întâmpla nimic;
• de tipul $2$: Să se afle energia maximă degajată într-o reacție nucleară între două zone active ale flatquarkon-ului. O zonă activă este o porțiune conexă a matricii (toți quarcii incluși sunt adiacenți) ce conține doar quarci activi și are dimensiune maximă (nu se mai poate adăuga niciun alt quark activ fără a încălca proprietatea de conexitate). Reamintiți-vă faimoasa formulă pentru echivalența masă-energie, $E=mc^2$. Astfel, energia degajată într-o reacție nucleară este egală cu suma maselor tuturor quarcilor din cele două zone (în $MeV$).

Date de intrare

Datele de intrare conţin pe prima linie $2$ numere întregi $N$ și $M$, separate printr-un spațiu, reprezentând dimensiunile matricei maselor.
Pe următoarele $N$ linii se află câte $M$ numere întregi, separate prin spații, reprezentând descrierea matricei maselor.
Următoarea linie conține numărul întreg $Q$, reprezentând numărul de instrucțiuni. Următoarele $Q$ linii conțin un număr întreg $t$, sau $3$ numere întregi separate prin spații $t$, $i$ și $j$. Dacă $t=1$, atunci se aplică un câmp magnetic asupra quarcului aflat pe linia $i$ și coloana $j$. Dacă $t=2$, se va afișa energia maximă degajată într-o reacție nucleară folosindu-ne de configurația actuală a flatquarkon-ului. Dacă o reacție este imposibilă, se va afișa $-1$.

Date de ieșire

Se va afișa răspunsul la toate instrucțiunile de tipul $2$, fiecare pe câte o linie.

Restricții și precizări

• $1 \leq N*M \leq 4*10^5$;
• $1 \leq Q \leq 2*10^5$;
• $1 \leq m_{ij} \leq 1 \ 000$;
• o zonă nu poate reacționa cu ea însuși;
• Subtask $1$ ($20$p): $N=M$ și $Q \leq 2 \ 000$;
• Subtask $2$ ($20$p): $Q \leq 2 \ 000$;
• Subtask $3$ ($20$p): $N=1$;
• Subtask $4$ ($40$p): Fără restricții suplimentare.

Exemplu

stdin

2 3 
1 2 3 
4 5 6 
8 
2 
1 1 1
1 2 2 
2 
1 2 1 
2 
1 1 3 
2

stdout

-1
6
-1
13

Explicație

• La prima instrucțiune de tipul $2$ nu avem nicio zonă activă, deci o reacție este imposibilă.
• La a doua instrucțiune de tipul $2$ avem două zone active $[1, 1]$ și $[2, 2]$. Energia degajată $1 + 5 = 6 \; MeV$.
• La a treia instrucțiune de tipul $2$ avem o singură zonă activă $[[1, 1], [2, 1], [2, 2]]$, o reacție este imposibilă.
• La a patra instrucțiune de tipul $2$ avem două zone active $[[1, 1], [2, 1], [2, 2]]$ și $[1, 3]$. Energia degajată este $1 + 4 + 5 + 3 = 13 \; MeV$.