_"He can call me a flower if he wants to... I don't mind... "_
După ce au ajutat la gonirea spiriduşilor de praf, Henry şi Hetty şi-au găsit o slujbă care să le testeze cu adevărat talentul la curăţenie. Mai exact, ei s-au angajat la o fermă de sconcşi nou înfiinţată. Aceasta este formată iniţial din $N$ cuşti goale, dispuse in linie. Pentru a începe activitatea de creştere a sconcşilor, ei vor avea de făcut $M$ operaţii de forma:

$1 c{~nr~} m{~nr~} p{~nr}~$: Henry şi Hetty aduc cel de-al nr-ulea sconcs la fermă, pe care îl pun în cuşca c{~nr~}. Acest sconcs are are miros m{~nr~} si coeficient de pierdere al mirosului p{~nr~}.

$1 c{~nr~} m{~nr~} p{~nr~}$: Henry şi Hetty aduc cel de-al nr-ulea sconcs la fermă, pe care îl pun în cuşca c{~nr~}. Acest sconcs are are miros m{~nr~} si coeficient de pierdere al mirosului p{~nr~}.

$2 l r$: Henry şi Hetty trebuie să afle care este mirosul minim dintr-o cuşcă aflată în intervalul $[l, r]$. Mirosul dintr-o cuşcă $y (1 ≤ y ≤ N)$ se defineşte ca fiind *max(m{~x~}-p {~x~}|y-c{~x~}|)*, pentru $1 ≤ x ≤ nr$, nr fiind numărul de sconcşi aduşi la fermă până la operaţia curentă.

* $1 ≤ N ≤ 200 000$
* $1 ≤ M ≤ 500 000$

* $1 ≤ cx ≤ N$, pentru fiecare operaţie de tip $1$.
* $1 ≤ mx, px ≤ 1 000 000 000$, pentru fiecare operaţie de tip $1$.

* $1 ≤ c{~x~} ≤ N$, pentru fiecare operaţie de tip $1$.
* $1 ≤ m{~x~}, p{~x~} ≤ 1 000 000 000$, pentru fiecare operaţie de tip $1$.

* $1 ≤ l ≤ r ≤ N$, pentru fiecare operaţie de tip $2$.
* Fiecare sconcs adus la fermă are un coeficient de pierdere al mirosului mai mare sau egal cu cel al sconcsului adus anterior. Cu alte cuvinte $p{~x~} ≤ p{~x+1~}$ pentru orice $x$, $1 ≤ x < nr$.
* Într-o cuşcă se pot afla mai mulţi sconcşi la un moment dat.