==Include(page="template/taskheader" task_id="datorii")==
==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 ≤ 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 ≤ Q ≤ 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:
* $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.
h2. Date de intrare
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).
h2. Date de iesire
In fisierul $datorii.out$ se vor scrie pe cate o linie sumele cerute de fiecare operatie de tip $B$ (sumele se cer in ordinea aparitiei operatiilor in fisierul de intrare).
h2. Restrictii si precizari
* $1 ≤ N ≤ 15 000$
* {$0 < M ≤ 100 000$}
* In orice moment, {$A{~i~}$} ({$1 ≤ i ≤ N$}) este nenegativ.
h2. Exemplu
table(example). |_. datorii.in|_. datorii.out|
|6 6
1 3 2 0 0 10
1 3 6
1 1 4
0 3 1
1 1 6
0 6 2
1 1 6
|12
6
15
13|
==Include(page="template/taskfooter" task_id="datorii")==
==Include(page="template/raw")==
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<=N<=15000) 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<=Q<=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 (numar natural, 0<M<=100 000), 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) sau 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.
h2. Date de Intrare
Fisierul datorii.in va contine pe prima linie numerele N si M. Pe urmatoarea linie se afla valorile sirului A_1, A_2, A_3...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) iar 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
In fisierul datorii.out se vor scrie pe cate o linie sumele cerute de fiecare operatie de tip B. (Sumele se cer in ordinea aparitiei operatiilor in fisierul de intrare.)
h2. Exemplu
datorii.in
6 6
1 3 2 0 0 10
1 3 6
1 1 4
0 3 1
1 1 6
0 6 2
1 1 6
datorii.out
12
6
15
13
Precizari
In orice moment, A_i (1<=i<=N) este nenegativ.
==Include(page="template/taskfooter" task_id="datorii")==
