Undo

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

1 – Update x y z : La valoarea elementului de pe linia $x$ și coloana $y$ se adună valoarea întreagă $z$.

2 – 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)$.

3 – 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 si precizări

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

Exemplu

undo.in

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

undo.out

2
16
6
7