410752: GYM104096 D Суммарный XOR

D. Суммарный XORограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Дана таблица неотрицательных целых чисел $$$N\times M$$$ ($$$N$$$ строк и $$$M$$$ столбцов) и размеры окна, накладываемого на эту таблицу: $$$n \times m$$$ ($$$n$$$ строк и $$$m$$$ столбцов, $$$1 \leq n \leq N,$$$ $$$1 \leq m \leq M$$$). Далее для всех возможных положений окна вычисляется XOR всех чисел, попавших в окно (определение операции приведено ниже). Затем вычисляется XOR всех полученных результатов для окон. Необходимо определить, какое число получится в результате.

Операция XOR (побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ) для двух целых чисел определяется следующим образом: числа представляются в двоичной системе счисления и вычисляется поразрядная сумма по модулю 2, в итоге получается двоичное представление результата операции. Например: $$$$$$ 5\,XOR\,3 = 101_2\,XOR\,011_2 = 110_2 = 6. $$$$$$ Операция XOR присутствует во многих языках программирования. Например, в языке Pascal для её вычисления используется оператор $$$xor,$$$ в языках C, C++, Python, Java оператор ^.

Нетрудно показать, что операция XOR ассоциативна и коммутативна, поэтому в условии не оговорено, в каком порядке проходятся все возможные положения окна и в каком порядке обходятся числа в окне при вычислении операции.

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

В первой строке входных данных записаны четыре целых числа в указанном порядке: $$$N,$$$ $$$M,$$$ $$$n,$$$ $$$m$$$ - размеры исходной таблицы и размеры окна ($$$1\leq n \leq N \leq 10^3,$$$ $$$1\leq m \leq M \leq 10^3$$$). В последующих $$$N$$$ строках записано по $$$M$$$ целых неотрицательных чисел, не превосходящих $$$2\cdot 10^9$$$ — элементы таблицы.

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

В качестве результата программа должна вывести единственное число — ответ на вопрос задачи.

Система оценки

Решение задачи оценивается независимо на каждом тесте. За каждый успешно пройденный тест, кроме тестов из условия, начисляется 2 балла. Прохождение тестов из условия является необходимым условием для оценивания задачи на остальных тестах. Остальные тесты оцениваются независимо друг от друга. Тесты разбиты на следующие группы тестов:

Номер группы	Описание	Тесты в группе	Балл за группу
0	Тесты из условия	1 – 2	0
1	Дополнительное ограничение: $$$1\leq n \leq N \leq 30,$$$ $$$1\leq m \leq M \leq 30$$$	3 – 12	20
2	Дополнительное ограничение: в таблице присутствуют только числа 0 и 1	13 – 22	20
3	Без дополнительных ограничений	23 – 52	60

ПримерыВходные данные

2 3 1 2
1 2 3
4 5 6

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

0

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

2 2 1 1
1 2
3 4

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

4