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}$ și 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 ( m_x - p_x \times |y - c_x| )$, 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 și 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 1 \ 000$ și $M \leq 3 \ 000$.

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