The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 198 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Iahub and Xors

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIahub 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:

- 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}). - 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.

Examples

Input

3 5

2 1 1 2 2 1

2 1 3 2 3 2

2 3 1 3 3 3

1 2 2 3 3

1 2 2 3 2

Output

3

2

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/07/2023 08:56:55 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|