A. Pet Shop
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The owner of the pet shop has noticed that more and more pets are becoming lazy. In particular, the pigs do nothing but sleep all day, so half of the problem setter's fee has been deducted. The cats, on the other hand, have gradually learned to do nothing except sing "Hachimi". In order to correct the bad habits in the shop and make sure the pets actually learn something real, the owner decides to open an arithmetic class for them.

One day, the owner arranges $$$n^2$$$ pets into $$$n$$$ rows and $$$n$$$ columns, forming an $$$n\times n$$$ grid. Both rows and columns are numbered $$$1,2,\cdots,n$$$. The owner decides to play a small game to test the pets' arithmetic ability. Each pet keeps an integer, which is initially $$$0$$$. The owner will then issue $$$m$$$ commands in order, of the following four types:

  • $$$\texttt{1 }k$$$: every pet adds $$$k$$$ to its number.
  • $$$\texttt{2 }x\texttt{ }k$$$: every pet in row $$$x$$$ adds $$$k$$$ to its number.
  • $$$\texttt{3 }y\texttt{ }k$$$: every pet in column $$$y$$$ adds $$$k$$$ to its number.
  • $$$\texttt{4 }x\texttt{ }y$$$: the pet at row $$$x$$$, column $$$y$$$ reports its number.
For each command of type 4, output the current number of that pet.

After you solve this problem, the owner would like to remind you that the problems are not arranged in order of difficulty.

Input

The first line contains two integers $$$n,m$$$ ($$$1\le n\le 2025$$$, $$$1\le m\le 10^6$$$).

Each of the next $$$m$$$ lines contains $$$2$$$ or $$$3$$$ integers, describing a single command in one of the formats given above.

In the commands, it is guaranteed that $$$1\le x,y\le n$$$ and $$$-10^9\le k\le 10^9$$$.

Output

For each command of type 4, output one line containing a single integer — the current number of the pet at row $$$x$$$, column $$$y$$$.

Examples
Input
3 5
1 9
2 3 -1
4 1 3
3 3 4
4 3 3
Output
9
12
Input
2025 10
4 1394 821
1 998244353
3 985 123456789
2 1024 987654321
3 996 996412345
4 1024 996
1 -1000000000
1 -1000000000
2 2025 -1919810
4 2025 985
Output
0
2982311019
-880218668
Note

In the first example:

  • The first command ($$$\texttt{1 9}$$$) changes the numbers of all pets from $$$\begin{bmatrix}0&0&0\\0&0&0\\0&0&0\end{bmatrix}$$$ to $$$\begin{bmatrix}\color{red}9&\color{red}9&\color{red}9\\\color{red}9&\color{red}9&\color{red}9\\\color{red}9&\color{red}9&\color{red}9\end{bmatrix}$$$.
  • The second command ($$$\texttt{2 3 -1}$$$) changes the numbers of all pets from $$$\begin{bmatrix}9&9&9\\9&9&9\\9&9&9\end{bmatrix}$$$ to $$$\begin{bmatrix}9&9&9\\9&9&9\\\color{red}8&\color{red}8&\color{red}8\end{bmatrix}$$$.
  • For the third command ($$$\texttt{4 1 3}$$$), the numbers of all pets are $$$\begin{bmatrix}9&9&\color{blue}9\\9&9&9\\8&8&8\end{bmatrix}$$$, so the pet at row $$$1$$$, column $$$3$$$ should answer $$$9$$$.
  • The fourth command ($$$\texttt{3 3 4}$$$) changes the numbers of all pets from $$$\begin{bmatrix}9&9&9\\9&9&9\\8&8&8\end{bmatrix}$$$ to $$$\begin{bmatrix}9&9&\color{red}{13}\\9&9&\color{red}{13}\\8&8&\color{red}{12}\end{bmatrix}$$$.
  • For the fifth command ($$$\texttt{4 3 3}$$$), the numbers of all pets are $$$\begin{bmatrix}9&9&13\\9&9&13\\8&8&\color{blue}{12}\end{bmatrix}$$$, so the pet at row $$$3$$$, column $$$3$$$ should answer $$$12$$$.