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

* $1 ≤ i ≤ N$.
* $0 ≤ x, k, h[i] ≤ 1000 000 000$.
* $1 ≤ l ≤ r ≤ N$.

* $N ≤ 1000, Q ≤ 1000, k = 1$.
* $N ≤ 80000, Q ≤ 80000, k = 1$.
* $N ≤ 1000, Q ≤ 1000$, nu există faze $magice$.
* Nu există faze $magice$.
* $l = 1, r = N$.
* $N ≤ 80000, Q ≤ 80000$.

* 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. Exemple

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}%

4
|

h3. Explicatie