D. Яхуб и Xor'ы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Яхубу не нравятся лирические отступления, так что он прямо скажет, что от Ваc требуется в данной задаче.

Дана матрица a, состоящая из n строк и n столбцов. Изначально все элементы в матрице равны 0. Как строки, так и столбцы матрицы 1-индексированные, то есть, строки нумеруются числами 1, 2, ..., n, и столбцы нумеруются числами 1, 2, ..., n. Обозначим элемент матрицы, который стоит на пересечении i-ой строки и j-ого столбца, как ai, j.

Будем называть подматрицей (x0, y0, x1, y1) элементы матрицы ai, j, такие, что выполняются два неравенства: x0 ≤ i ≤ x1, y0 ≤ j ≤ y1.

Напишите программу, которая выполняет операции двух следующих типов:

  1. Query(x0, y0, x1, y1): вывести xor всех элементов подматрицы (x0, y0, x1, y1).
  2. Update(x0, y0, x1, y1, v): каждый элемент подматрицы (x0, y0, x1, y1) xor-ится со значением v, то есть элемент подматрицы b заменяется на b xor v.
Входные данные

Первая строка содержит два целых числа: n (1 ≤ n ≤ 1000) и m (1 ≤ m ≤ 105). Целое число m обозначает количество операций, которые нужно выполнить. Каждая из m следующих строк содержит пять или шесть целых чисел, в зависимости от типа текущей операции.

Если i-ая операция из входных данных — это query (запрос), первое число i-ой строки будет равно 1. За единицей будут идти четыре целых числа x0, y0, x1, y1. Если же i-ая операция — это операция update, первое число в i-ой строке будет равно 2. За двойкой будут идти пять целых чисел x0, y0, x1, y1, v.

Гарантируется, что для каждой операции update выполняется следующее неравенство: 0 ≤ v < 262. Гарантируется, что для каждой операции выполняются следующие неравенства: 1 ≤ x0 ≤ x1 ≤ n, 1 ≤ y0 ≤ y1 ≤ n.

Выходные данные

Для каждой операции query выведите результат в отдельной строке.

Примеры
Входные данные
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
Выходные данные
3
2
Примечание

После первых 3-x операций, матрица будет выглядеть следующим образом: 


1 1 2
1 1 2
3 3 3

Чтобы выполнить четвертую операцию нужно посчитать 1 xor 2 xor 3 xor 3 = 3.

Чтобы выполнить пятую операцию нужно посчитать 1 xor 3 = 2.