==Include(page="template/taskheader" task_id="datorii")==

Tatal si mama lui Gigel se ocupa cu vanzarea de sisteme de calcul. Afacerea s-a dovedit a fi foarte profitabila datorita unui sistem incredibil de creditare a clientilor: un client care cumpara un calculator in ziua $X$ (in acest moment au trecut $N$ zile de la infiintarea magazinului, zilele se numeroteaza de la 1 la $N$, {$0<X&le;N$}) poate returna banii oricand doreste acesta, neexistand o limita de timp impusa. Astfel, aproape in fiecare zi, la magazinul familiei se prezinta diversi clienti care achita integral sau partial un sistem de calcul cumparat in zilele anterioare. Deoarece vor sa inceapa o noua afacere, Mama si Tata doresc sa il insarcineze pe Gigel cu administrarea magazinului de calculatoare. Pentru aceasta Gigel trebuie sa indeplineasca o conditie esentiala: in orice moment al sederii lui la magazin el poate fi solicitat prin telefon de catre tatal sa raspunda cat mai repede la urmatoarea familie de intrebari: ce suma de bani a ramas inca neachitata luand in considerare achizitiile facute de clienti in zilele $P$, $P+1$, {$P+2$}... {$Q-1$}, {$Q$} ({$0<P&le;Q&le;N$}). Se stie ca niciodata nu s-au cumparat doua calculatoare in aceeasi zi. Ajuta-l pe Gigel sa demonstreze parintilor ca poate administra magazinul.

Tatal si mama lui Gigel se ocupa cu vanzarea de sisteme de calcul. Afacerea s-a dovedit a fi foarte profitabila datorita unui sistem incredibil de creditare a clientilor: un client care cumpara un calculator in ziua $X$ (in acest moment au trecut $N$ zile de la infiintarea magazinului, zilele se numeroteaza de la 1 la $N$, {$0 < X &le; N$}) poate returna banii oricand doreste acesta, neexistand o limita de timp impusa. Astfel, aproape in fiecare zi, la magazinul familiei se prezinta diversi clienti care achita integral sau partial un sistem de calcul cumparat in zilele anterioare. Deoarece vor sa inceapa o noua afacere, Mama si Tata doresc sa il insarcineze pe Gigel cu administrarea magazinului de calculatoare. Pentru aceasta Gigel trebuie sa indeplineasca o conditie esentiala: in orice moment al sederii lui la magazin el poate fi solicitat prin telefon de catre tatal sa raspunda cat mai repede la urmatoarea familie de intrebari: ce suma de bani a ramas inca neachitata luand in considerare achizitiile facute de clienti in zilele $P$, $P+1$, {$P+2$}... {$Q-1$}, {$Q$} ({$0 < P &le; Q &le; N$}). Se stie ca niciodata nu s-au cumparat doua calculatoare in aceeasi zi. Ajuta-l pe Gigel sa demonstreze parintilor ca poate administra magazinul.

h2. Cerinta

Se dau: $N$, $M$, un sir de numere {$A{~1~}$}, {$A{~2~}$}... {$A{~N~}$} si $M$ operatii. {$A{~i~}$} ({$1≤A{~i~}≤1000$}, {$1≤i≤N$}) reprezinta suma de bani inca neachitata pentru o comanda efectuata in ziua $i$. O operatie poate fi de doua feluri:

Se dau: $N$, $M$, un sir de numere {$A{~1~}$}, {$A{~2~}$}... {$A{~N~}$} si $M$ operatii. {$A{~i~}$} ({$1 ≤ A{~i~} ≤ 1000$}, $1 ≤ i ≤ N$) reprezinta suma de bani inca neachitata pentru o comanda efectuata in ziua $i$. O operatie poate fi de doua feluri:

* $A$ (achitare - se scade o valoare din suma restanta a unei zile anume)
* $B$ (interogare - se cere suma tuturor sumelor restante ale unui interval de zile). Programul trebuie sa scrie in fisierul de iesire suma ceruta de fiecare operatie de tip $B$ in momentul interogarii.

Fisierul $datorii.in$ va contine pe prima linie numerele $N$ si $M$. Pe urmatoarea linie se afla valorile sirului {$A{~1~}$}, {$A{~2~}$}... {$A{~N~}$} separate prin cate un spatiu. Urmatoarele $M$ linii descriu operatiile (achitari sau interogari) efectuate in ordinea data. Fiecare linie care descrie o operatie incepe cu un cod binar (un numar intreg cu valoarea 0 sau 1) si continua cu 2 numere intregi.

* Un cod 0 urmat de doua numere intregi $T$, $V$ ({$1≤T≤N$}, {$1≤V≤1000$}) reprezinta o operatie de tip $A$ (in momentul respectiv s-a achitat o valoare $V$ din suma restanta a zilei $T$)
* Un cod 1 urmat de doua numere intregi $P$, $Q$ ({$1≤P≤Q≤N$}) o operatie de tip $B$ (se cere suma tuturor sumelor restante din zilele $P$, {$P+1$}, {$P+2$}... $Q$ in momentul respectiv).

* Un cod 0 urmat de doua numere intregi $T$, $V$ ({$1 ≤ T ≤ N$}, {$1 ≤ V ≤ 1000$}) reprezinta o operatie de tip $A$ (in momentul respectiv s-a achitat o valoare $V$ din suma restanta a zilei $T$)
* Un cod 1 urmat de doua numere intregi $P$, $Q$ ({$1 ≤ P ≤ Q ≤ N$}) o operatie de tip $B$ (se cere suma tuturor sumelor restante din zilele $P$, {$P+1$}, {$P+2$}... $Q$ in momentul respectiv).

h2. Date de iesire

* $1 ≤ N ≤ 15 000$
* {$0 < M &le; 100 000$}

* In orice moment, {$A{~i~}$} ({$1≤i≤N$}) este nenegativ.

* In orice moment, {$A{~i~}$} ({$1 ≤ i ≤ N$}) este nenegativ.

h2. Exemplu

15
13|

==Include(page="template/taskfooter" task_id="datorii")==

==Include(page="template/taskfooter" task_id="datorii")==
 
 
 

34