== include(page="template/taskheader" task_id="flower") ==

Poveste şi cerinţă...

_"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~.
 
_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

Fişierul de intrare $flower.in$ ...

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

Î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.
* Î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.

h2. Exemplu

table(example). |_. flower.in |_. flower.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. flower.in |_. flower.out |_. Explicatie |
| 4 6
1 3 5 2
1 1 8 3
2 1 4
1 4 10 4
2 3 4
2 1 2
| 3
6
5
| Cele 6 operaţii au următoarele semnificaţii:
1. Este adus în cuşca 3 un sconcs care are mirosul 5 şi coeficient de pierdere al mirosului 2.
2. Este adus în cuşca 1 un sconcs care are mirosul 8 şi coeficient de pierdere al mirosului 3.
3. Acum, cuşca cu miros minim din intervalul [1, 4] este cuşca 4, în care mirosul are valoarea 3.
4. Este adus în cuşca 4 un sconcs care are mirosul 10 şi coeficient de pierdere al mirosului 4.
5. Acum, cuşca cu miros minim din intervalul [3, 4] este cuşca 3, în care mirosul are valoarea 6.
6. Acum, cuşca cu miros minim din intervalul [1, 2] este cuşca 2, în care mirosul are valoarea 5.
|

== include(page="template/taskfooter" task_id="flower") ==