小Z самостійно вивчає квантові комп'ютери. Нещодавно, досліджуючи розділ про квантовий зв'язок, він натрапив на цікаву задачу. Alice і Bob здійснюють квантовий зв'язок. Мовою їхнього спілкування є словник $S$ розміру $n$, у якому кожне слово $s_i$ ($1\le i\le n$) можна подати двійковим рядком довжини $256$. У цій задачі $s_i$ можна згенерувати викликом функції gen, з якою можна ознайомитися у файлі gen.cpp у каталозі задачі. Параметри цієї функції $n,a_1,a_2$ задані у вхідних даних.

Alice і Bob планують здійснити $m$ передач. Під час кожної Alice надсилає Bob рівно одне слово зі словника. Проте канал зв'язку ненадійний і зазнає впливу шуму. Точніше, позначимо початкове слово, яке Alice передає під час $i$-ї передачі, через $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$ бітів. Якщо можливо, що Eve не втручався, виведіть $1$, інакше — $0$. Bob дуже довіряє вашим здібностям, тому ви маєте відповідати на запити в режимі онлайн; точні вимоги наведено в розділі вхідних даних.

Щоб зменшити час зчитування, рядки, які отримав Bob, задано шістнадцятковими рядками довжини $64$. Вони складаються з цифр 0–9 і великих латинських літер A–F, причому літери A–F позначають відповідно значення $10$–$15$. Кожну шістнадцяткову цифру можна перетворити на двійковий рядок: наприклад, 5 відповідає 0101, A — 1010, а C — 1100.

Вхідні дані

Зчитайте дані з файлу qi.in.

Перший рядок містить чотири невід'ємні цілі числа $n,m,a_1,a_2$ — розмір словника, кількість передач і початкові значення параметрів $a_1$ та $a_2$ функції gen відповідно.

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

Кожен із наступних $m$ рядків містить шістнадцятковий рядок довжини $64$ і невід'ємне ціле число $k_i$ — остаточний двійковий рядок, який отримав Bob під час $i$-ї передачі, та поріг шумових спотворень відповідно.

Щоб змусити вас відповідати на запити в режимі онлайн, після перетворення шістнадцяткового рядка на двійковий рядок довжини $256$ слід застосувати XOR кожного біта з $lastans$. Лише тоді ви отримаєте справжній двійковий рядок, який отримав Bob під час цієї передачі. Тут $lastans\in\{0,1\}$ — відповідь на попередній запит; перед першим запитом початкове значення $lastans$ дорівнює $0$.

Зауважте: для зчитування або виведення змінних типу unsigned long long за допомогою функцій scanf і printf відповідний специфікатор — llu.

Вихідні дані

Виведіть результат у файл qi.out.

Виведіть $m$ рядків, кожен з одним цілим числом $0$ або $1$ — відповіддю на поточний запит.

Приклад запитів

Щоб пояснити умову, розглянемо спрощений випадок: слова словника задано явно, їхню довжину зменшено до $4$, а відповідати на запити дозволено офлайн.

Нехай словник має розмір $n=2$ і містить слова 1010 та 0111.

Для запиту $\texttt{B}=\texttt{1011}$ і $k_1=1$ відповідь має бути $1$: рядок можна отримати, змінивши четвертий біт слова 1010 (біти рахуємо від старшого до молодшого; так само й далі).

Для запиту $\texttt{1}=\texttt{0001}$ і $k_2=2$ відповідь має бути $1$: рядок можна отримати, змінивши другий і третій біти слова 0111.

Для запиту $\texttt{1}=\texttt{0001}$ і $k_3=1$ відповідь має бути $0$.

• Змінивши щонайбільше один біт слова 1010, можна отримати 1010, 0010, 1110, 1000, 1011.
• Змінивши щонайбільше один біт слова 0111, можна отримати 0111, 1111, 0011, 0101, 0110.
• Отримати $\texttt{1}=\texttt{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]$.