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:

\begin{enumerate}
\item 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.
\item 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$.
\item 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$.
\end{enumerate}

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

(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?

\section{Protocol de Interacţiune}

h2. Date de intrare
 
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 iesire
 
Se vor afisa raspunsurile pentru toate fazele de inspectie, fiecare pe cate un rand.
 
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$.

Concurentul trebuie să implementeze următoarele patru funcţii:

h2. Exemple

\begin{lstlisting}
void initialise(int N, int Q, int h[]);
void cut(int l, int r, int k);
void magic(int i, int x);
long long int inspect(int l, int r);
\end{lstlisting}
 
Funcţiei \texttt{initialise} îi sunt date $N$ (numărul copacilor), $Q$ (numărul intrărilor din orar), şi un vector $h$, unde $h[i]$ este înălţimea celui de-al $i$ copac, pentru $1 \leq i \leq N$. Această funcţie este apelată de către sursa comisiei exact o singură dată, înainte ca oricare dintre celelalte trei funcţii să fie apelate. Funcţiile \texttt{cut}, \texttt{magic} şi \texttt{inspect} reprezintă fazele de tăiere a copacilor, magică şi respectiv de inspecţie a copacilor, şi sunt caracterizate de respectivii lor parametrii. Implementarea concurentului a funcţiei \texttt{inspect} trebuie să returneze suma înălţimilor copacilor cu poziţii între $l$ şi $r$.
 
Concurentul nu trebuie să implementeze funcţia \texttt{main}. Aceasta va fi implementată în fişierul comisiei \texttt{grader.cpp}; veţi primi un exemplu \texttt{grader.cpp} în ataşamente. Funcţia noastră \texttt{main} va citi $N$, $Q$, secvenţa celor $N$ înălţimi iniţiale, şi cele $Q$ intrări din orar. Cele trei tipuri de intrări din orar (\texttt{cut(l, r, k)}, \texttt{magic(i, x)} şi \texttt{inspect(l, r)}) sunt codificate ca \texttt{1 l r k}, \texttt{2 i x} şi respectiv \texttt{3 l r}. Acesta este formatul fişierului de intrare ce va fi folosit în exemplele de mai jos.
 
Observaţi că îi este permis concurentului să folosească variabile globale, funcţii suplimentare, metode şi clase.
 
\newpage
 
\begin{restrictions}[
\begin{itemize}
\item $1 \leq N, Q \leq \np{300000}$
\item Se garantează faptul că funcţiile \texttt{cut}, \texttt{magic} şi \texttt{inspect} vor fi apelate de exact $Q$ ori în total.
\item $1 \leq i \leq N$
\item $0 \leq x, k, h\lbrack i\rbrack \leq \np{1000000000}$
\item $1 \leq l \leq r \leq N$
\end{itemize}
]
\restr{5}{$N \leq \np{1000}, Q \leq \np{1000}, k = 1$}
\restr{8}{$N \leq \np{80000}, Q \leq \np{80000}, k = 1$}
\restr{8}{$N \leq \np{1000}, Q \leq \np{1000}$, nu există faze \texttt{magice}.}
\restr{19}{Nu există faze \texttt{magice}.}
\restr{10}{$l = 1, r = N$}
\restr{21}{$N \leq \np{80000}, Q \leq \np{80000}$}
\restr{29}{Nu există alte restricţii suplimentare.}
\end{restrictions}
 
\begin{examples}%
\exmp{%
6 10

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

1 2 3 1 2 3
1 1 6 3
3 1 6

2 1 1000
3 1 6
1 1 3 999

3 1 5}{
9

3 1 5
| 9

6
5
1005

4}%
\end{examples}

4
|

\section{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 ş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ă.
 
\end{document}
 
h2. Date de intrare
 
Fişierul de intrare $weirdtree.in$ ...
 
h2. Date de ieşire
 
În fişierul de ieşire $weirdtree.out$ ...
 
h2. Restricţii
 
* $... ≤ ... ≤ ...$
 
h2. Exemplu
 
table(example). |_. weirdtree.in |_. weirdtree.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

Î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") ==