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 ai, j.

We will call a submatrix (x0, y0, x1, y1) such elements ai, j for which two inequalities hold: x0 ≤ i ≤ x1, y0 ≤ j ≤ y1.

Write a program to perform two following operations:

  1. Query(x0, y0, x1, y1): print the xor sum of the elements of the submatrix (x0, y0, x1, y1). 
  2. Update(x0, y0, x1, y1, v): each element from submatrix (x0, y0, x1, y1) gets xor-ed by value v. 

Input

The first line contains two integers: n (1 ≤ n ≤ 1000) and m (1 ≤ m ≤ 105). 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 x0, y0, x1, y1. 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 x0, y0, x1, y1, v. 

It is guaranteed that for each update operation, the following inequality holds: 0 ≤ v < 262. It is guaranteed that for each operation, the following inequalities hold: 1 ≤ x0 ≤ x1 ≤ n, 1 ≤ y0 ≤ y1 ≤ 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. 
#include <bits/stdc++.h>
using namespace std;
const int N = 1002;
const int M = 123;
const double Pi = acos(-1);
const long long Inf = 1e18;
const int inf = 1e9;
const int mod = 1e9 + 7;
void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int mult(int a, int b) { return 1ll * a * b % mod; }
int n, m, t[2][2][N][N];
int get(int x, int y) {
  int ans = 0;
  for (int i = x; i > 0; i = (i & (i + 1)) - 1) {
    for (int j = y; j > 0; j = (j & (j + 1)) - 1) {
      ans ^= t[x & 1][y & 1][i][j];
    }
  }
  return ans;
}
void upd(int x, int y, int v) {
  for (int i = x; i <= n; i = (i | (i + 1))) {
    for (int j = y; j <= n; j = (j | (j + 1))) {
      t[x & 1][y & 1][i][j] ^= v;
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int it = 0; it < m; it++) {
    int t, x1, y1, x2, y2, v;
    scanf("%d%d%d%d%d", &t, &x1, &y1, &x2, &y2);
    if (t == 1) {
      int ans =
          get(x2, y2) ^ get(x1 - 1, y1 - 1) ^ get(x1 - 1, y2) ^ get(x2, y1 - 1);
      printf("%d\n", ans);
    } else {
      scanf("%d", &v);
      upd(x1, y1, v);
      upd(x2 + 1, y1, v);
      upd(x1, y2 + 1, v);
      upd(x2 + 1, y2 + 1, v);
    }
  }
  return 0;
}
