== include(page="template/taskheader" task_id="flower") ==
_"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:

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

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

h2. Date de intrare

Pe prima linie a fişierului de intrare *flower.in* se vor afla două numere naturale N şi M, cu semnificaţia din enunţ. Pe următoarele M linii se vor afla descrierile celor M operaţii. Primul număr de pe fiecare linie, tip, semnifică tipul operaţiei. Dacă tip = 1, pe linia respectivă se vor mai afla trei numere naturale c ~nr~, m ~nr~, p ~nr~ semnificând faptul că al nr-ulea sconcs, adus în cuşca c ~nr~, are miros m ~nr~ şi coeficient de pierdere al mirosului p ~nr~. Dacă tip = 2, pe linia respectivă se vor mai afla două numere naturale l r, semnificând faptul că Henry şi Hetty trebuie să afle care este mirosul minim dintr-o cusca aflată în intervalul [l, r].

Pe prima linie a fişierului de intrare *flower.in* se vor afla două numere naturale $N$ şi $M$, cu semnificaţia din enunţ. Pe următoarele $M$ linii se vor afla descrierile celor $M$ operaţii. Primul număr de pe fiecare linie, $tip$, semnifică tipul operaţiei. Dacă $tip = 1$, pe linia respectivă se vor mai afla trei numere naturale $c{~nr~}, m{~nr~}, p{~nr~}$ semnificând faptul că al $nr$-ulea sconcs, adus în cuşca $c{~nr~}$, are miros $m{~nr~}$ şi coeficient de pierdere al mirosului $p{~nr~}$. Dacă $tip = 2$, pe linia respectivă se vor mai afla două numere naturale $l r$, semnificând faptul că Henry şi Hetty trebuie să afle care este mirosul minim dintr-o cusca aflată în intervalul $[l, r]$.

h2. Date de ieşire

În fişierul de ieşire *flower.out* se vor afişa în ordine, câte unul pe linie, răspunsurile la operaţiile de tip 2 citite din fişierul de intrare.

În fişierul de ieşire *flower.out* se vor afişa în ordine, câte unul pe linie, răspunsurile la operaţiile de tip $2$ citite din fişierul de intrare.

h2. Restricţii

* 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 ≤ 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 px ≤ px+1 pentru orice x, 1 ≤ x < nr.

* $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 ≤ 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.

* Răspunsul la fiecare operaţie de tip 2 va putea fi reprezentat ca un întreg pe 64 de biţi cu semn.
* Răspunsul la o operaţie de tip 2 poate fi şi negativ.
* Pentru 20% din teste N ≤ 1000 şi M ≤ 3000.

* Răspunsul la fiecare operaţie de tip $2$ va putea fi reprezentat ca un întreg pe $64$ de biţi cu semn.
* Răspunsul la o operaţie de tip $2$ poate fi şi negativ.
* Pentru $20%$ din teste $N ≤ 1000$ şi $M ≤ 3000$.

h2. Exemplu