undo

Undo

== include(page="template/taskheader" task_id="undo") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $undo.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $undo.out$ ...

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

h2. 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!$

h2. Exemplu
table(example). |_. undo.in |_. undo.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 11
1 1 1 2
1 2 3 1
2 1 3
1 3 2 4
1 2 2 10
2 3 2
3 2
1 1 1 3
2 5 5
3 3
2 4 4
| 2
16
6
7

|

h3. Explicaţie
...

== include(page="template/taskfooter" task_id="undo") ==