Устав вычислять ответы на всевозможные необычные задачи по модулю $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, верен.