Problem I
Slottsmur

Ägaren av slottet Drakfjälls Kastell är rädd för att hans slott ska bli belägrat. Om detta sker vill han att muren ska vara tålig, så han planerar att förstärka den. Slottsmuren består av $N$ murbitar som står på en linje. Varje murbit har en viss höjd. Nedan visas ett exempel av hur muren kan se ut.

Slottsägaren är även lite oroad för att hans mur ska drabbas av fuktskador när det regnar, som potentiellt kan förvärras om han förstärker den. När det regnar kommer alla murens tomrum att fyllas upp med vatten, så länge vattnet inte kan rinna av vid sidorna. Om det hade regnat på föregående exempelmur hade vatten samlats vid de blå rutorna.

För att kunna vara strategisk med sin ombyggnad vill han veta hur vissa förstärkningar hade påverkat mängden regnvatten som samlas i muren om en del av den hade rivts i en belägring. Till sitt förfogande har han dig, slottets teoretiska datalog. Slottsägaren kommer att ställa dig två sorters frågor:

• Givet är två värden $l$ och $r$. Om alla murbitar rivs förutom de i intervallet $[l,r]$, hur mycket regnvatten hade samlats i muren om det börjar regna? Notera att muren inte faktiskt rivs, så detta påverkar inte framtida frågor.

• Givet två värden $i$ och $w$, öka höjden på den $i$:te murbiten med $w$. Detta är en permanent förändring som kommer att påverka framtida frågor.

Indata

Den första raden i indatan innehåller heltalen $N$ och $Q$ ($1 \le N, Q \le 2 \cdot 10^5$), antalet murbitar i muren och antalet frågor.

Därefter följer $N$ heltal $h_1, h_2, \dots , h_N$ ($1 \leq h_i \leq 10^9$), höjden på varje murbit.

De följande $Q$ raderna beskriver alla frågor. Varje fråga börjar med heltalet $T$, som antingen är $1$ eller $2$.

• Om $T=1$ följer $l, r$ ($1 \leq l \leq r \leq N$). Du ska då skriva ut svaret på en fråga av sort $1$ som beskrivet ovan.

• Om $T=2$ följer $i, w$ ($1 \leq i \leq N$, $1 \leq w \leq 10^9$). Du ska då öka höjden på den $i$:te murbiten med $w$. Det är garanterat att höjden av murbiten förblir mindre än eller lika med $10^9$ efter detta.

Utdata

För varje fråga av sort $1$, skriv ut mängden vatten som samlas om det börjar regna efter att alla murbitar som ligger utanför det givna intervallet rivs.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall 1

Vid första frågan ombes vi att beräkna mängden vatten som samlas om vi river allt utanför $[1,6]$. Eftersom $[1,6]$ utgör hela muren, så rivs inget.

Vid andra frågan undrar Slottsägaren vad som händer om en del av den högra änden av muren rivits. De murbitarna som hade rivits markeras med mörgrått.

Vid tredje frågan höjs en del av muren. Detta påverkar den fjärde frågan, som ser ut som följande.

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

5
1
7

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

4
3
1