== 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:
$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ă.
Poveste şi cerinţă...
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]$.
Fişierul de intrare $flower.in$ ...
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$ ...
h2. Restricţii
* $1 ≤ N ≤ 200 000$
* $1 ≤ M ≤ 500 000$
* $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.
* 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 |_. 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.
|
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
...
== include(page="template/taskfooter" task_id="flower") ==
