Fişierul intrare/ieşire:	datorii.in, datorii.out	Sursă	info-arena 1.0
Autor	Cristian George Strat	Adăugată de
Timp execuţie pe test	0.075 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	2/5

Vezi solutiile trimise | Statistici

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.

Cerinta

Se dau: N, M, un sir de numere A₁, A₂... 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.

Date de intrare

Fisierul datorii.in va contine pe prima linie numerele N si M. Pe urmatoarea linie se afla valorile sirului A₁, A₂... 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).

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).

Restrictii si precizari

• 1 ≤ N ≤ 15 000
• 0 < M ≤ 100 000
• In orice moment, A_i (1 ≤ i ≤ N) este nenegativ.

Exemplu

Cum se trimit solutii?