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

У Кроша есть матрица из $$$n$$$ строк, пронумерованных от $$$0$$$ до $$$n - 1$$$, и $$$m$$$ столбцов, пронумерованных от $$$0$$$ до $$$m - 1$$$. Элемент в левой верхней ячейке равен $$$x$$$: $$$a_{00} = x$$$, где $$$x$$$ – заданное число. Остальные значения матрицы вычисляются следующим способом. Матрица заполняется сверху вниз, слева направо: сначала заполняется $$$0$$$-я строка, затем $$$1$$$-я и т. д. Строки заполняются слева направо. Значение в каждой ячейке вычисляется следующим образом: $$$a_{ij} = \oplus$$$ (всех уже заполненных к этому моменту значений матрицы) $$$\oplus i \oplus j$$$, где $$$\oplus$$$ – операция побитового исключающего ИЛИ – ксор. Вам нужно ответить на множество запросов. В каждом запросе вам даны числа $$$n, m, x, y$$$. Выведите в ответе на этот запрос $$$1$$$, если в матрице Кроша размера $$$n$$$ на $$$m$$$, левое верхнее значение которой равно $$$x$$$, есть элемент, равный $$$y$$$, и $$$0$$$ в противном случае.

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

В первой строке вам дано число $$$1 \le t \le 10^4$$$ – количество запросов. В каждой из следующих $$$t$$$ строк вам дано четыре числа $$$1 \le n \le 10^9, 1 \le m \le 10^9, 0 \le x \le 10^9, 0 \le y \le 10^9$$$.

Система оценки
  • Подзадача 1 (20 баллов) $$$t \le 10, n \le 10, m \le 10$$$
  • Подзадача 2 (25 баллов) ограничения на $$$t$$$ нет, $$$n \le 1000$$$, $$$m \le 1000$$$, дополнительно гарантируется, что все $$$m$$$ равны между собой и что все $$$x$$$ равны между собой
  • Подзадача 3(10 баллов) ограничения на $$$t$$$ нет, $$$n \le 1000$$$, $$$m \le 1000$$$, дополнительно гарантируется, что все $$$m$$$ равны между собой($$$x$$$ могут отличаться), необходимые подзадачи – 2
  • Подзадача 4 (45 баллов) без дополнительных ограничений, необходимые подзадачи – 1, 2, 3
Выходные данные

Выведите ответы на запросы в том порядке, в котором они заданы во входных данных.

Пример
Входные данные
3
1 1 10 10
2 2 3 2
3 3 5 10
Выходные данные
1
1
0