XOR множества \(\{s_1,s_2,\ldots,s_m\}\) определяется как \(s_1 \oplus s_2 \oplus \ldots \oplus s_m\), где \(\oplus\) обозначает побитовую операцию XOR.
Почти выиграв IOI, Виктор купил себе сетку размером \(n\times n\), содержащую целые числа в каждой ячейке. \(n\) — четное число. Целое число в \(i\)-й строке и \(j\)-м столбце равно \(a_{i,j}\).
К сожалению, Mihai украл сетку у Виктора и сказал ему, что вернет ее только с одним условием: Виктор должен сообщить Mihai XOR всех чисел сетки.
Виктор не помнит все элементы сетки, но он помнит некоторую информацию о ней: для каждой ячейки Виктор помнит XOR всех соседних ячеек.
Две клетки считаются соседними, если они имеют общую сторону — другими словами, для некоторых целых чисел \(1 \le i, j, k, l \le n\) ячейка в \(i\)-й строке и \(j\)-м столбце является соседом ячейки в \(k\)-й строке и \(l\)-м столбце, если \(|i - k| = 1\) и \(j = l\), или если \(i = k\) и \(|j - l| = 1\).
Чтобы вернуть свою сетку, Виктор просит вас о помощи. Можете ли вы, используя информацию, которую помнит Виктор, найти XOR всей сетки?
Можно доказать, что ответ определяется однозначно.
Выходные данные
Для каждого набора входных данных выведите одно целое число — XOR всей сетки.
Примечание
Для первого набора входных данных одна из возможных исходных сеток Виктора:
Для второго набора входных данных одна из возможных исходных сеток Виктора:
| \(3\) | \(8\) | \(8\) | \(5\) |
| \(9\) | \(5\) | \(5\) | \(1\) |
| \(5\) | \(5\) | \(9\) | \(9\) |
| \(8\) | \(4\) | \(2\) | \(9\) |
Для третьего набора входных данных одна из возможных исходных сеток Виктора:
| \(4\) | \(3\) | \(2\) | \(1\) |
| \(1\) | \(2\) | \(3\) | \(4\) |
| \(5\) | \(6\) | \(7\) | \(8\) |
| \(8\) | \(9\) | \(9\) | \(1\) |
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1 5
5 1
4
1 14 8 9
3 1 5 9
4 13 11 1
1 15 4 11
4
2 4 1 6
3 7 3 10
15 9 4 2
12 7 15 1
|
4
9
5
|