Description

You have an $N \times N$ board with an integer in each cell, all initially $0$. You need to support three types of operations:

• 1 x y A $1\le x,y\le N$, and $A$ is a positive integer. Add $A$ to the number in cell x, y.
• 2 x1 y1 x2 y2 $1 \le x_1 \le x_2 \le N$, $1 \le y_1\le y_2 \le N$. Output the sum of numbers inside the rectangle $x_1, y_1, x_2, y_2$.
• 3 None. Terminate the program.

Input Format

The first line contains a positive integer $N$.

Each of the following lines contains one operation. For every command, all numbers after the first one must be XORed with the previous output answer last_ans. Initially, last_ans $= 0$.

Output Format

For each operation of type $2$, output the corresponding answer.

4
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3

3
5

Hint

Constraints: $1\leq N\leq 5\times 10^5$, the number of operations does not exceed $2\times 10^5$, memory limit $20\texttt{MB}$. It is guaranteed that answers fit in the range of int and that after decoding the testdata remains valid.

Translated by ChatGPT 5