小 Z самостоятельно изучает квантовые компьютеры. Недавно, читая раздел о квантовой связи, он встретил интересную задачу. Alice и Bob обмениваются квантовыми сообщениями. Их язык общения — словарь $S$ размера $n$, каждое слово $s_i$, где $1\le i\le n$, представляется двоичной строкой длины 256 бит. В этой задаче $s_i$ можно сгенерировать вызовом функции gen, код которой находится в файле gen.cpp в каталоге задачи. Параметры функции n, a1, a2 задаются во входных данных.

Alice и Bob собираются провести $m$ сеансов связи. В каждом сеансе Alice передаёт Bob ровно одно слово из словаря. Однако канал связи ненадёжен и подвержен шуму. Точнее, пусть в $i$-м сеансе исходное слово Alice равно $x_i$. Шум может инвертировать не более $k_i$ битов этой двоичной строки. Иными словами, строка $y_i$, полученная Bob, может отличаться от $x_i$ не более чем в $k_i$ позициях и может отсутствовать в словаре $S$.

При этом Bob узнал, что злодей Eve проник в их канал связи и намерен мешать общению. Он может заменить полученную Bob строку на произвольную двоичную строку длины 256 бит, которая также может отсутствовать в словаре $S$. Eve очень хитёр и необязательно вмешивается в каждый сеанс.

Bob обратился к вам за помощью. Для каждого следующего сеанса по окончательно полученной Bob строке и порогу шума $k_i$, где $0\le k_i\le 15$, определите, возможно ли, что Eve не вмешивался. Это означает, что полученную строку можно получить из некоторого слова словаря, инвертировав не более $k_i$ битов. Если такое возможно, выведите $1$, иначе $0$. Bob очень верит в ваши способности, поэтому отвечать нужно в режиме онлайн; подробности приведены в разделе входных данных.

Чтобы сократить время ввода, полученная Bob строка задаётся шестнадцатеричной строкой длины 64. Она содержит цифры 0–9 и прописные английские буквы A–F, обозначающие соответственно значения от $10$ до $15$.

Шестнадцатеричную строку можно преобразовать в двоичную посимвольно: например, 5 соответствует 0101, A — 1010, C — 1100.

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

Данные считываются из файла qi.in.

Первая строка содержит четыре неотрицательных целых числа $n,m,a_1,a_2$ — размер словаря, количество сеансов связи и начальные значения параметров a1 и a2 функции gen соответственно.

В своей программе нужно вызвать упомянутую в условии функцию gen, чтобы сгенерировать словарь. Можно скопировать и использовать код из gen.cpp. Булев массив s[N+1][256] в программе содержит все слова.

Следующие $m$ строк содержат по одной шестнадцатеричной строке длины 64 и неотрицательному целому числу $k_i$ — окончательную строку, полученную Bob в $i$-м сеансе, и порог шума соответственно.

Чтобы обеспечить ответы в режиме онлайн, после восстановления двоичной строки длины 256 бит из шестнадцатеричной нужно выполнить побитовое исключающее ИЛИ каждого бита с $lastans$. Только после этого получится настоящая строка, полученная Bob в этом сеансе. Здесь $lastans\in\{0,1\}$ — ответ на предыдущий запрос; перед первым запросом $lastans=0$.

Обратите внимание: при вводе и выводе переменных типа unsigned long long с помощью scanf и printf используется спецификатор llu.

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

Результат выводится в файл qi.out.

Выведите $m$ строк, в каждой — одно целое число $0$ или $1$, ответ на текущий запрос.

Пример запросов

Для удобства объяснения рассмотрим упрощённый случай: слова словаря заданы явно, их длина уменьшена до 4, и разрешены ответы на запросы в режиме офлайн.

Пусть размер словаря $n=2$, а его слова — 1010 и 0111.

Для запроса B = 1011 и $k_1=1$ ответ равен $1$: строка получается инвертированием четвёртого бита 1010. Здесь и далее биты считаются от старшего к младшему.

Для запроса 1 = 0001 и $k_2=2$ ответ равен $1$: строка получается инвертированием второго и третьего битов 0111.

Для запроса 1 = 0001 и $k_3=1$ ответ равен $0$.

• Инвертировав не более 1 бита в 1010, можно получить 1010, 0010, 1110, 1000, 1011.
• Инвертировав не более 1 бита в 0111, можно получить 0111, 1111, 0011, 0101, 0110.
• Получить 1 = 0001 невозможно: эта строка обязательно является результатом вмешательства Eve.

Примеры

Пример 1

См. файлы qi/qi1.in и qi/qi1.ans в каталоге участника.

Пример 2

См. файлы qi/qi2.in и qi/qi2.ans в каталоге участника.

Пример 3

См. файлы qi/qi3.in и qi/qi3.ans в каталоге участника.

Ограничения

Для всех тестов $1\le n\le 4\times 10^5$, $1\le m\le 1.2\times 10^5$, $0\le k\le 15$. Значения $a_1$ и $a_2$ генерируются равномерно случайно в диапазоне $[0,2^{64}-1]$.