Cerința

Se citesc de la tastură două numere naturale n și m, apoi un șir de n numere naturale. Asupra șirului de numere se pot aplica m operații de două feluri: modificarea unei valori din șir și respectiv determinarea sumei valorilor din șir aflate între două poziții date.

Date de intrare

Programul citește de la tastatură două numere naturale n și m și cele n numere naturale ale șirului, separate prin spații. Apoi se citesc cele m operații care se vor aplica șirului de valori. Pentru fiecare operație se citesc trei valori op, x, y cu următoarea semnificație:

• dacă op=1 atunci se va modifica valoarea de la poziția x din șir cu valoarea y;
• dacă op=2 atunci se va afișa suma valorilor din șir aflate între poziția x și y;

Date de ieșire

Programul va afișa pe ecran pe fiecare linie o valoare S, reprezentând suma valorilor de la operațiile de tipul 2.

Restricții și precizări

• 1 ≤ n, m ≤ 100.000
• cele n numere din șirul de valori vor fi mai mici decât 1.000.000.000
• numerotarea pozițiilor în șir va începe de la 1
• 1 ≤ x ≤ y ≤ n

Exemplu:

Intrare

5 5
1 2 3 4 5
2 1 5
1 3 4
2 1 5
1 4 10
2 3 5

Ieșire

15
16
19