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₀,y₀,x₁,y₁) such elements a_i,j for which two inequalities hold: x₀≤i≤x₁, y₀≤j≤y₁.

Write a program to perform two following operations:

1. Query(x₀, y₀, x₁, y₁): print the xor sum of the elements of the submatrix (x₀,y₀,x₁,y₁).
2. Update(x₀, y₀, x₁, y₁, v): each element from submatrix (x₀,y₀,x₁,y₁) gets xor-ed by value v.

The first line contains two integers: n (1≤n≤1000) and m (1≤m≤10⁵). 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₀, y₀, x₁, y₁. 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₀, y₀, x₁, y₁, v.

It is guaranteed that for each update operation, the following inequality holds: 0≤v<2⁶². It is guaranteed that for each operation, the following inequalities hold: 1≤x₀≤x₁≤n, 1≤y₀≤y₁≤n.

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