Cansado de calcular las respuestas a problemas extraños módulo $998244353$ o $10^9+7$, 小E ha diseñado un acertijo relacionado con el número $2$:

Dada una cuadrícula de $2$ filas y $2^k$ columnas, debes colocar los números del $1$ al $2^{k+1}$ en sus $2^{k+1}$ casillas, sin omitir ni repetir ninguno, de modo que las relaciones de orden entre casillas adyacentes cumplan las siguientes restricciones.

En concreto, se dan tres secuencias binarias $a,b,c$ de longitudes $2^k-1$, $2^k$ y $2^k-1$, respectivamente. Una matriz $A$ de tamaño $2\times2^k$ es una solución del acertijo si y solo si satisface simultáneamente estas cuatro condiciones:

1. $A$ contiene cada entero de $1,2,\ldots,2^{k+1}$ exactamente una vez.
2. Para todo $1\le i<2^k$, se cumple $a_i=[A_{1,i}<A_{1,i+1}]$.
3. Para todo $1\le i\le2^k$, se cumple $b_i=[A_{1,i}<A_{2,i}]$.
4. Para todo $1\le i<2^k$, se cumple $c_i=[A_{2,i}<A_{2,i+1}]$.

Aquí, $[P]$ vale $1$ si la condición $P$ se cumple, y $0$ en caso contrario.

Encontrar una solución cualquiera o determinar que no existe ninguna sería demasiado fácil para ti. Como este acertijo trata sobre el número $2$, 小E te pide calcular el número de soluciones módulo $2$.

小E ha preparado $t$ acertijos con cuadrículas del mismo tamaño y los ha comprimido juntos mediante un método eficiente. Debes calcular, para cada uno de ellos, el número de soluciones módulo $2$.

Detalles de implementación

No debes ni necesitas implementar la función main.

Asegúrate de que el programa enviado incluya el archivo de cabecera puzzle.h; para ello, añade al principio:

#include "puzzle.h"

Debes implementar la siguiente función en el archivo fuente que envíes:

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

• $t,k$ indican, respectivamente, el número de acertijos y el tamaño de la cuadrícula.
• Para $0\le i<2^k-1$, el bit $j$ ($0\le j<t$) de la representación binaria de $a_i$ indica la restricción de orden entre $A_{1,i+1}$ y $A_{1,i+2}$ en el acertijo $j+1$.
• Para $0\le i<2^k$, el bit $j$ ($0\le j<t$) de la representación binaria de $b_i$ indica la restricción de orden entre $A_{1,i+1}$ y $A_{2,i+1}$ en el acertijo $j+1$.
• Para $0\le i<2^k-1$, el bit $j$ ($0\le j<t$) de la representación binaria de $c_i$ indica la restricción de orden entre $A_{2,i+1}$ y $A_{2,i+2}$ en el acertijo $j+1$.
• La función debe devolver un entero no negativo cuyo bit $j$ ($0\le j<t$) indique el número de soluciones del acertijo $j+1$ módulo $2$.
• En cada caso de prueba, la biblioteca de interacción llamará a esta función exactamente una vez.

Atención: en cualquier circunstancia, el tiempo de ejecución de la biblioteca de interacción no superará los $0.1$ segundos. Su consumo de memoria es fijo y no supera los $64$ MiB.

Cómo probar tu programa

El archivo grader.cpp del directorio del problema es una implementación de referencia de la biblioteca de interacción. La implementación utilizada en la evaluación final será distinta; por tanto, tu solución no debe depender de la implementación de la biblioteca.

Puedes compilar un ejecutable con el siguiente comando en el directorio del problema:

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

El ejecutable compilado funciona así:

• Lee de la entrada estándar los datos con este formato:

  • La primera línea contiene dos enteros positivos $t,k$, que indican el número de acertijos y el tamaño de la cuadrícula.
  • La línea $3i-1$ ($1\le i\le t$) contiene una cadena binaria $a_1\ldots a_{2^k-1}$ de longitud $2^k-1$.
  • La línea $3i$ ($1\le i\le t$) contiene una cadena binaria $b_1\ldots b_{2^k}$ de longitud $2^k$.
  • La línea $3i+1$ ($1\le i\le t$) contiene una cadena binaria $c_1\ldots c_{2^k-1}$ de longitud $2^k-1$.

• Escribe en la salida estándar los datos con este formato:

  • Se escriben $t$ líneas. La línea $i$ ($1\le i\le t$) contiene un entero no negativo que indica el número de soluciones del acertijo $i$ módulo $2$.

Ejemplos

Entrada 1

2 1
1
01
1
1
00
1

Salida 1

1
0

Entrada 2

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

Salida 2

1
1
0
0

Archivos adjuntos

Entre los archivos adjuntos:

1. grader.cpp es la implementación de referencia proporcionada de la biblioteca de interacción.
2. puzzle.h es el archivo de cabecera; no necesitas preocuparte por su contenido.
3. template_puzzle.cpp es el código de ejemplo proporcionado, que puedes consultar para implementar tu propio código.

Subtareas

Todos los datos de prueba cumplen:

• $1\le t\le32$, $1\le k\le18$.
• Para todo $1\le i<2^k$, se cumple $a_i\in\{0,1\}$.
• Para todo $1\le i\le2^k$, se cumple $b_i\in\{0,1\}$.
• Para todo $1\le i<2^k$, se cumple $c_i\in\{0,1\}$.

Propiedad especial A: $t\le4$.

Propiedad especial B: para todo $1\le i<2^k$, se cumple $b_i\ne b_{i+1}$.

Subtareas

Atención:

• No debes obtener información interna de la biblioteca de interacción por medios no permitidos, como interactuar directamente con los flujos de entrada y salida estándar. Tales acciones se considerarán trampas.
• La biblioteca de interacción de la evaluación final tiene una implementación diferente de la biblioteca de ejemplo.

Este problema está sujeto, en primer lugar, a las mismas restricciones que los problemas tradicionales. Por ejemplo, un error de compilación hace que todo el problema reciba $0$ puntos; un error de ejecución o superar el límite de tiempo o memoria hace que el caso de prueba correspondiente reciba $0$ puntos. El programa solo puede acceder a las variables que hayas definido y a las proporcionadas por la biblioteca de interacción. Intentar acceder a otros espacios de direcciones puede provocar errores de compilación o de ejecución.

Bajo las condiciones anteriores:

• Para cada caso de prueba, el programa obtiene la puntuación máxima si y solo si la respuesta devuelta al llamar a puzzle es correcta.