Олимпиадный тренинг

Задача . D. Яхуб и Xor'ы

Задача

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

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

Будем называть подматрицей (x₀, y₀, x₁, y₁) элементы матрицы a_i, j, такие, что выполняются два неравенства: x₀ ≤ i ≤ x₁, y₀ ≤ j ≤ y₁.

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

Query(x₀, y₀, x₁, y₁): вывести xor всех элементов подматрицы (x₀, y₀, x₁, y₁).
Update(x₀, y₀, x₁, y₁, v): каждый элемент подматрицы (x₀, y₀, x₁, y₁) xor-ится со значением v, то есть элемент подматрицы b заменяется на b xor v.

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

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

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

Гарантируется, что для каждой операции update выполняется следующее неравенство: 0 ≤ v < 2⁶². Гарантируется, что для каждой операции выполняются следующие неравенства: 1 ≤ x₀ ≤ x₁ ≤ n, 1 ≤ y₀ ≤ y₁ ≤ n.