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

Poveste şi cerinţă...

Azusa, vrăjitoarea zonelor înalte, a descoperit o grădină plină de copaci ciudaţi! Astfel, împreună cu prietena ei, Laika, s-a decis să petreacă nişte timp acolo, având grijă de grădină.
 
Grădina poate fi văzută ca o secvenţă cu $N$ copaci, în care copacii sunt numerotaţi de la $1$ la $N$. Fiecare copac are o anumită înălţime număr natural. Astfel Azusa îşi va petrece timpul în concordanţă cu un orar ce conţine $Q$ intrări, care pot fi de mai multe feluri:
 
* O fază de tăiere a copacilor, caracterizată de trei numere întregi $l$, $r$, şi $k$. În această fază, Azusa îşi va petrece următoarele $k$ zile tăind copaci. În fiecare zi ea găseşte cel mai înalt copac al cărei poziţii este cuprinsă între $l$ şi $r$ şi îi scade acestuia înălţimea cu 1. În cazul în care există mai  mulţi astfel de copaci de înălţime maximă, ea îl alege pe cel mai din stânga. Dacă cel mai înalt copac are înălţimea $0$, atunci nimic nu se întâmplă în acea zi.
* O fază magică, caracterizată de două numere întregi $i$ şi $x$. În această fază, Azusa modifică copacul de pe poziţia $i$, astfel încât acesta să aibă înălţimea $x$.
* O fază de inspecţie a copacilor, caracterizată de două numere întregi $l$ şi $r$. În această fază, Azusa va găsi suma înălţimilor copacilor ce au poziţiile cuprinse între $l$ şi $r$.
 
(Observaţi că termenul "cuprinse" înseamnă inclusiv capetele; de exemplu, $1, 2, 3, 4, 5$ sunt "cuprinse" între $1$ şi $5$.)
 
Azusa este curioasă care vor fi rezultatele fazelor de inspecţie a copacilor şi vrea să le ştie fără să fie nevoită să parcurgă întreg orarul de una singură. Puteţi să o ajutaţi voi?

h2. Date de intrare

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

Pe primul rand al fisierului de intrare $weirdtree.in$ se vor citi $N$, $Q$. Pe al doilea rand urmeaza secvenţa celor $N$ înălţimi iniţiale. Urmeaza $Q$ randuri fiecare cu cate o intrare din orar. Cele trei tipuri de intrări din orar (taietura, magic si inspect) sunt codificate ca $1 l r k$, $2 i x$ şi respectiv $3 l r$.

h2. Date de ieşire

h2. Date de iesire

În fişierul de ieşire $weirdtree.out$ ...

Se vor afisa raspunsurile pentru toate fazele de inspectie, fiecare pe cate un rand.

h2. Restricţii

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N, Q ≤ 300 000$.
* Se garantează faptul că funcţiile $cut$, $magic$ şi $inspect$ vor fi apelate de exact $Q$ ori în total.
* $1 ≤ i ≤ N$.
* $0 ≤ x, k, h[i] ≤ 1000 000 000$.
* $1 ≤ l ≤ r ≤ N$.
* Pentru 8 puncte, $N ≤ 1000, Q ≤ 1000, k = 1$.
* Pentru alte 8 puncte, $N ≤ 80000, Q ≤ 80000, k = 1$.
* Pentru alte 8 puncte, $N ≤ 1000, Q ≤ 1000$, nu există faze $magice$.
* Pentru alte 16 puncte, Nu există faze $magice$.
* Pentru alte 8 puncte, $l = 1, r = N$.
* Pentru alte 20 de puncte, $N ≤ 80000, Q ≤ 80000$.

h2. Exemplu

h2. Exemple

table(example). |_. weirdtree.in |_. weirdtree.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 10
1 2 3 1 2 3
1 1 6 3
3 1 6
1 1 3 3
3 1 6
1 1 3 1000
3 1 6
2 1 1000
3 1 6
1 1 3 999
3 1 5
| 9
6
5
1005
4

|

h3. Explicaţie

h3. Explicatie
 
În prima fază, după fiecare dintre cele $3$ zile de tăiere de copaci, înălţimile copacilor sunt $1, 2, 2, 1, 2, 3$; $1, 2, 2, 1, 2, 2$; şi $1, 1, 2, 1, 2, 2$. Suma acestor valori este $9$, care este răspunsul la inspecţia din a doua fază.
 
În a treia fază, după fiecare dintre cele $3$ zile de tăiere de copaci, înălţimile copacilor sunt $1, 1, 1, 1, 2, 2$; $0, 1, 1, 1, 2, 2$; şi $0, 0, 1, 1, 2, 2$. Suma acestor valori este $6$, care este răspunsul la inspecţia din a patra fază.
 
În a cincea fază, după fiecare din cele $1000$ de zile de tăiere de copaci, înălţimile copacilor sunt $0, 0, 0, 1, 2, 2$. Aceasta deoarece un copac cu înălţime $0$ nu poate fi tăiat. Suma acestor valori este $5$, care este răspunsul la inspecţia din faza a şasea.
 
În a şaptea fază, primul copac este crescut la înălţimea $1000$, rezultând în înălţimile $1000, 0, 0, 1, 2, 2$. Suma acestor valori este $1005$, care este răspsunul la inspecţia din a opta fază.

...

În a noua fază, fiecare dintre cele $999$ de zile de tăiere de copaci reduce înălţimea primului copac cu $1$. Asta ne dă următoarele înălţimi de copaci $1, 0, 0, 1, 2, 2$ la sfârşitul fazei. Suma primelor cinci valori dintre acestea este $4$, care este răspunsul la inspecţia din a zecea fază -- faza finală.

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