E. XOR-сетка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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 всей сетки?

Можно доказать, что ответ определяется однозначно.

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

Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество тестов. Далее следует описание тестовых случаев.

Первая строка каждого набора входных данных содержит единственное четное целое число $$$n$$$ ($$$2 \leq n \leq 1000$$$) — размер сетки.

Далее следуют $$$n$$$ строк, каждая из которых содержит $$$n$$$ целых чисел. $$$j$$$-е число в $$$i$$$-й строке представляет собой XOR всех чисел, записанных в соседях ячейки в $$$i$$$-й строке и $$$j$$$-м столбце.

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$1000$$$ и в исходной сетке $$$0 \leq a_{i, j} \leq 2^{30} - 1$$$.

Формат взлома

Чтобы взломать решение, используйте следующий формат:

Первая строка должна содержать единственное целое число t ($$$1 \le t \le 100$$$) — количество тестов.

Первая строка каждого набора входных данных должна содержать единственное четное целое число $$$n$$$ ($$$2 \leq n \leq 1000$$$) — размер сетки.

Далее должны следовать $$$n$$$ строк, каждая из которых содержит $$$n$$$ целых чисел. $$$j$$$-е целое число в $$$i$$$-й из этих строк равно $$$a_{i,j}$$$ в исходной сетке Виктора. Значения в сетке должны быть целыми числами в диапазоне $$$[0, 2^{30}-1]$$$.

Сумма $$$n$$$ по всем тестам не должна превышать $$$1000$$$.

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

Для каждого набора входных данных выведите одно целое число — XOR всей сетки.

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

Для первого набора входных данных одна из возможных исходных сеток Виктора:

$$$1$$$$$$3$$$
$$$2$$$$$$4$$$

Для второго набора входных данных одна из возможных исходных сеток Виктора:

$$$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$$$