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-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/16/2021 21:25:11 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|