Втомившись обчислювати відповіді на всілякі дивні задачі за модулем $998244353$ або $10^9+7$, маленький E придумав головоломку, пов’язану з числом 2.

Дано сітку з 2 рядків і $2^k$ стовпців. Потрібно заповнити її $2^{k+1}$ клітинок числами від 1 до $2^{k+1}$ без повторів і пропусків так, щоб співвідношення між числами в сусідніх клітинках задовольняли наведені нижче обмеження.

А саме, дано три послідовності з нулів і одиниць $a,b,c$ довжини $2^k-1$, $2^k$ і $2^k-1$ відповідно. Матриця $A$ розміру $2\times2^k$ є розв’язком головоломки тоді й лише тоді, коли одночасно виконуються чотири умови:

1. $A$ містить кожне ціле число $1,2,\ldots,2^{k+1}$ рівно один раз.
2. Для всіх $1\le i<2^k$ виконується $a_i=[A_{1,i}<A_{1,i+1}]$.
3. Для всіх $1\le i\le2^k$ виконується $b_i=[A_{1,i}<A_{2,i}]$.
4. Для всіх $1\le i<2^k$ виконується $c_i=[A_{2,i}<A_{2,i+1}]$.

Тут $[P]$ дорівнює 1, якщо умова $P$ істинна, і 0 інакше.

Просто знайти довільний розв’язок або визначити, що розв’язку немає, для вас надто легко. Оскільки головоломка стосується числа 2, маленький E просить обчислити кількість її розв’язків за модулем 2.

Маленький E підготував $t$ головоломок з однаковим розміром сітки й ефективно стиснув їх разом. Для кожної головоломки потрібно знайти кількість розв’язків за модулем 2.

Деталі реалізації

Вам не потрібно й не слід реалізовувати функцію main.

Переконайтеся, що подана програма підключає заголовок puzzle.h, додавши на початку:

#include "puzzle.h"

У вихідному файлі поданої програми потрібно реалізувати функцію:

unsigned puzzle(int t, int k, std::vector<unsigned> a,
    std::vector<unsigned> b, std::vector<unsigned> c);

• $t,k$ задають кількість головоломок і розмір сітки відповідно.
• Для $0\le i<2^k-1$ біт $j$ ($0\le j<t$) двійкового запису $a_i$ задає обмеження на співвідношення між $A_{1,i+1}$ та $A_{1,i+2}$ у головоломці $j+1$.
• Для $0\le i<2^k$ біт $j$ ($0\le j<t$) двійкового запису $b_i$ задає обмеження на співвідношення між $A_{1,i+1}$ та $A_{2,i+1}$ у головоломці $j+1$.
• Для $0\le i<2^k-1$ біт $j$ ($0\le j<t$) двійкового запису $c_i$ задає обмеження на співвідношення між $A_{2,i+1}$ та $A_{2,i+2}$ у головоломці $j+1$.
• Функція має повернути невід’ємне ціле число, у якому біт $j$ ($0\le j<t$) двійкового запису дорівнює кількості розв’язків головоломки $j+1$ за модулем 2.
• Для кожного тесту бібліотека взаємодії викликає цю функцію рівно один раз.

Увага: за будь-яких обставин час роботи бібліотеки взаємодії не перевищує 0.1 секунди; обсяг використаної нею пам’яті сталий і не перевищує 64 MiB.

Тестування програми

Файл grader.cpp у каталозі задачі є еталонною реалізацією бібліотеки взаємодії. Реалізація для остаточного тестування відрізнятиметься, тому ваш розв’язок не повинен залежати від реалізації бібліотеки.

У каталозі задачі можна скомпілювати виконуваний файл командою:

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -static

Для отриманого виконуваного файлу:

Програма читає зі стандартного вводу дані такого формату:

• Перший рядок містить два додатні цілі числа $t,k$, що задають кількість головоломок і розмір сітки відповідно.
• Рядок $3i-1$ ($1\le i\le t$) містить рядок з нулів і одиниць $a_1\ldots a_{2^k-1}$ довжини $2^k-1$.
• Рядок $3i$ ($1\le i\le t$) містить рядок з нулів і одиниць $b_1\ldots b_{2^k}$ довжини $2^k$.
• Рядок $3i+1$ ($1\le i\le t$) містить рядок з нулів і одиниць $c_1\ldots c_{2^k-1}$ довжини $2^k-1$.

Програма виводить у стандартний вивід дані такого формату:

• Усього $t$ рядків; рядок $i$ ($1\le i\le t$) містить невід’ємне ціле число — кількість розв’язків головоломки $i$ за модулем 2.

Приклади

Вхідні дані 1

2 1
1
01
1
1
00
1

Вихідні дані 1

1
0

Вхідні дані 2

4 2
100
1111
100
100
0000
110
110
1111
011
010
0000
010

Вихідні дані 2

1
1
0
0

Додаткові файли

Серед додаткових файлів:

1. grader.cpp — надана еталонна реалізація бібліотеки взаємодії.
2. puzzle.h — заголовковий файл; вам не потрібно знати його конкретний вміст.
3. template_puzzle.cpp — наданий приклад коду, на основі якого можна реалізувати власний код.

Підзадачі

Для всіх тестових даних:

• $1\le t\le32$, $1\le k\le18$;
• для всіх $1\le i<2^k$ виконується $a_i\in\{0,1\}$;
• для всіх $1\le i\le2^k$ виконується $b_i\in\{0,1\}$;
• для всіх $1\le i<2^k$ виконується $c_i\in\{0,1\}$.

Особлива властивість A: $t\le4$.

Особлива властивість B: для всіх $1\le i<2^k$ виконується $b_i\ne b_{i+1}$.

Оцінювання

Увага:

• Не можна отримувати внутрішню інформацію бібліотеки взаємодії недозволеними способами, наприклад безпосередньо взаємодіяти зі стандартними потоками вводу та виводу. Такі дії вважатимуться шахрайством.
• Реалізації бібліотеки для остаточного оцінювання та бібліотеки для прикладів відрізняються.

На цю задачу спочатку поширюються ті самі обмеження, що й на звичайні задачі: наприклад, помилка компіляції дає 0 балів за всю задачу; помилка виконання, перевищення обмеження часу або пам’яті тощо дає 0 балів за відповідний тест. У програмі можна звертатися лише до визначених вами змінних і змінних, наданих бібліотекою взаємодії. Спроба звернутися до інших адресних просторів може призвести до помилки компіляції або виконання.

За наведених вище умов:

• За кожен тест програма отримує повний бал тоді й лише тоді, коли відповідь, повернута викликом puzzle, правильна.