Ako se dobro sećate, gazda Srba ima voćnjak šljiva u srcu Šumadije. Kako je Srba veliki perfekcionista, on svoj šljivik održava uvek u formi kvadrata, tako da u svakom od ukupno N redova šljivika bude tačno po N stabala šljiva. Svako stablo ima svoju visinu, koju gazda Srba uredno kontroliše.

Kada se Srba popne na neku šljivu, on vidi vrhove svih šljiva u voćnjaku koje imaju manju visinu od one na koju se popeo (vrhove ostalih šljiva ne vidi). Njega zanima, kada se popne na neku šljivu, koji je najdalji vrh koji on vidi. Srba rastojanje između dve šljive meri kao zbir apsolutnih razlika redova i kolona u kojima se nalaze. Vremenom će se i visine nekih šljiva promeniti (gazda Srba može da ih poseče ili kalemi sa ciljem da bolje rode sledeće godine), ali će vas blagovremeno obavestiti o svim promenama visina.

Formalnije, gazda Srba će vam dostaviti Q informacija. Informacija može da bude tipa "1 X Y" što označava da se gazda Srba popeo na šljivu koja se nalazi u redu X i koloni Y , na ovu informaciju vi njemu treba da odgovorite koliko je udaljena najdalja šljiva čiji vrh on trenutno vidi; drugi tip informacije je "2 X Y V", što označava da je šljiva koja se nalazi u redu X i koloni Y promenila visinu na V.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U ulaznoj datoteci se u prvom redu nalazi broj N (1 ≤ N ≤ 1000), broj redova i kolona Srbinog voćnjaka. U sledećih N redova se nalaze po N brojeva iz intervala [1, 10⁹] koji predstavljaju početne visine svake šljive. U sledećem redu se nalazi broj Q (1 ≤ Q ≤ 500.000), broj Srbinih informacija. U sledećih Q redova se nalaze gore opisane informacije, u svakom redu po jedna. (1 ≤ X,Y ≤ N, 1 ≤ V ≤ 10⁹).

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) Za svaku informaciju prvog tipa ispisati udaljenost najudaljenije šljive čiji vrh gazda Srba vidi kada se popne na tu šljivu. Ukoliko ne postoji šljiva manja od one na koju se on popeo, ispisati -1.

Primer 1.

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

3
5
7
-1
5

Objašnjenje. Gazda Srba vam daje prvu informaciju da se popeo na šljivu (5, 1). On sada vidi vrhove šljiva (4, 1) i (4, 3). Šljiva (4, 1) se nalazi na udaljenosti 1 dok se šljiva (4, 3) nalazi na udaljenosti 3, pa je rezultat 3. Druga informacija je da je šljiva (5, 1) promenila visinu na 3. Treća informacija takođe kaže da se Srba popeo na šljivu (5, 1), ali sada on vidi vrhove šljiva (2, 3), (3, 3), (4, 1), (4, 3), (4, 5), od kojih su najudaljeniji (2, 3) i (4, 5) i nalaze se na udaljenosti 5. Za petu informaciju najudaljenija šljiva je (2, 5), za šestu nema šljive koja ima visinu manju od 1 pa je odgovor -1, a za poslednju informaciju najudaljenija manja šljiva je (4, 1).

Napomena.
U 50% test primera, Srba vam nikad neće dati informaciju drugog tipa. U ovim primerima je Q neparno, a tamo gde ima i informacija drugog tipa je Q parno.