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 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 \leq y \leq N$) se definește ca fiind: $max(mx – p_x * \lvert y – c_x \rvert$), pentru $1 \leq x \leq nr$, $nr$ fiind numărul de sconcși aduși la fermă până la operația curentă.

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

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.

Restricții si precizări

• $ 1 \leq N \leq 200 000$
• $ 1 \leq M \leq 500 000$
• $ 1 \leq c_x \leq N$, pentru fiecare operație de tip $1$.
• $1 \leq m_x, p_x \leq 1 000 000 000$, pentru fiecare operație de tip $1$.
• $1 \leq l \leq r \leq 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 \leq p_{x+1}$ pentru orice $x$, $1 \leq 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 \leq 1000$ și $M \leq 3000$.

Exemplu

flower.in

4 6
1 3 5 2
1 1 8 3
2 1 4
1 4 10 4
2 3 4
2 1 2

flower.out

3
6
5

Explicație

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