Undo

Bossanip vă dă o matrice $N \times 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