Fişierul intrare/ieşire:	undo.in, undo.out	Sursă	Lot Mehedinți 2015 - Baraj 5 Seniori
Autor	Andrei Heidelbacher, Eugenie Daniel Posdarascu	Adăugată de	Tatomir Alex •atatomir
Timp execuţie pe test	0.5 sec	Limită de memorie	45056 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Undo

Bossanip vă dă o matrice N * N iniţial plină cu 0. Se pot executa asupra ei 3 tipuri de operaţii:

• Update x y z: La valoarea elementului de pe linia x şi coloana y se adună valoarea întreagă z.
• Query x y: Se cere suma elementelor din submatricea determinată de colţul stânga-sus (1,1) şi colţul dreapta-jos (x,y).
• Undo x: Elimină ultimele x operaţii de Update şi Undo.

Se dau M astfel de operatii.

Date de intrare

Pe prima linie a fişierului de intrare undo.in se va afla un număr natural N şi un număr natural M. Pe următoarele M linii vor fi cele M operaţii ( 1 x y z pentru Update; 2 x y pentru Query; 3 x pentru Undo)

Date de ieşire

În fişierul de ieşire undo.out se va afisa răspunsul pentru fiecare operaţie de tip Query, câte unul pe linie.

Restricţii

• 1 ≤ N ≤ 520
• 1 ≤ M ≤ 500 000
• Se garantează că la operatiile de tip Undo x au existat cel puţin x operatii de Update şi Undo înainte.
• 1 ≤ z ≤ 2 000, pentru orice operaţie de tip 1
• L-aţi uitat pe Tassadar!

Exemplu

Cum se trimit solutii?