Iahub does not like background stories, so he'll tell you exactly what this problem asks you for.

You are given a matrix $*a*$ with $*n*$ rows and $*n*$ columns. Initially, all values of the matrix are zeros. Both rows and columns are 1-based, that is rows are numbered 1, 2, ..., $*n*$ and columns are numbered 1, 2, ..., $*n*$. Let's denote an element on the $*i*$-th row and $*j*$-th column as $*a*_{*i*, *j*}$.

We will call a submatrix $(*x*_{0}, *y*_{0}, *x*_{1}, *y*_{1})$ such elements $*a*_{*i*, *j*}$ for which two inequalities hold: $*x*_{0} ≤ *i* ≤ *x*_{1}$, $*y*_{0} ≤ *j* ≤ *y*_{1}$.

Write a program to perform two following operations:

1. Query($*x*_{0}$, $*y*_{0}$, $*x*_{1}$, $*y*_{1}$): print the xor sum of the elements of the submatrix $(*x*_{0}, *y*_{0}, *x*_{1}, *y*_{1})$.
2. Update($*x*_{0}$, $*y*_{0}$, $*x*_{1}$, $*y*_{1}$, $*v*$): each element from submatrix $(*x*_{0}, *y*_{0}, *x*_{1}, *y*_{1})$ gets xor-ed by value $*v*$.

Input

The first line contains two integers: $*n*$ ($1 ≤ *n* ≤ 1000$) and $*m*$ ($1 ≤ *m* ≤ 10^{5}$). The number $*m*$ represents the number of operations you need to perform. Each of the next $*m*$ lines contains five or six integers, depending on operation type.

If the $*i*$-th operation from the input is a query, the first number from $*i*$-th line will be 1. It will be followed by four integers $*x*_{0}$, $*y*_{0}$, $*x*_{1}$, $*y*_{1}$. If the $*i*$-th operation is an update, the first number from the $*i*$-th line will be 2. It will be followed by five integers $*x*_{0}$, $*y*_{0}$, $*x*_{1}$, $*y*_{1}$, $*v*$.

It is guaranteed that for each update operation, the following inequality holds: $0 ≤ *v* < 2^{62}$. It is guaranteed that for each operation, the following inequalities hold: $1 ≤ *x*_{0} ≤ *x*_{1} ≤ *n*$, $1 ≤ *y*_{0} ≤ *y*_{1} ≤ *n*$.

Output

For each query operation, output on a new line the result.

Note

After the first $3$ operations, the matrix will look like this:

1 1 2
1 1 2
3 3 3

The fourth operation asks us to compute 1 xor 2 xor 3 xor 3 = 3.

The fifth operation asks us to compute 1 xor 3 = 2.