小 Z está aprendiendo por su cuenta sobre ordenadores cuánticos. Al estudiar recientemente el capítulo de comunicación cuántica, ha encontrado un problema interesante. Alice y Bob se comunican mediante un diccionario $S$ de tamaño $n$, en el que cada palabra $s_i$ ($1\le i\le n$) se representa mediante una cadena binaria de 256 bits. En este problema, las palabras $s_i$ pueden generarse llamando a la función gen, que puedes consultar en gen.cpp, en el directorio del problema. Los parámetros $n,a_1,a_2$ de esta función se dan en la entrada.

Alice y Bob van a realizar $m$ comunicaciones, en cada una de las cuales Alice transmite a Bob exactamente una palabra del diccionario. Sin embargo, su canal no es fiable y está sujeto al ruido. Concretamente, en la transmisión $i$, sea $x_i$ la palabra original enviada por Alice. El ruido puede invertir como máximo $k_i$ bits de esta cadena. En otras palabras, si $y_i$ es la cadena que recibe Bob, puede diferir de $x_i$ en como máximo $k_i$ posiciones, y puede que $y_i$ no aparezca en el diccionario $S$.

Además, Bob descubre que el malvado Eve se ha infiltrado en su canal y pretende interferir en las comunicaciones. Puede cambiar la cadena recibida por Bob por cualquier cadena binaria de 256 bits, que tampoco tiene por qué aparecer en $S$. Eve es muy astuto y no necesariamente interfiere en todas las comunicaciones.

Bob te pide ayuda: para cada comunicación, dadas la cadena final que recibe y su umbral de ruido $k_i$ ($0\le k_i\le 15$), debes determinar si es posible que no haya sufrido la interferencia de Eve. Es decir, si la cadena recibida puede obtenerse invirtiendo como máximo $k_i$ bits de alguna palabra del diccionario. Si es posible que Eve no haya interferido, imprime $1$; de lo contrario, imprime $0$. Bob confía mucho en ti, así que debes responder a las consultas en línea, según los requisitos de la entrada.

Para reducir el tiempo de lectura, la cadena recibida por Bob se da como una cadena hexadecimal de longitud 64. Contiene los dígitos 0 a 9 y las letras mayúsculas A a F, que representan, respectivamente, los valores $10$ a $15$.

La cadena hexadecimal se puede convertir dígito a dígito en una cadena binaria. Por ejemplo, 5 corresponde a 0101, A a 1010 y C a 1100.

Entrada

Lee los datos del archivo qi.in.

La primera línea contiene cuatro enteros no negativos $n,m,a_1,a_2$: el tamaño del diccionario, el número de comunicaciones y los valores iniciales de los parámetros $a_1,a_2$ de la función gen.

Debes llamar en tu programa a la función gen mencionada en la descripción para generar el diccionario. Puedes copiar y utilizar el código de gen.cpp. El arreglo booleano s[N+1][256] del programa contiene todas las palabras.

Cada una de las siguientes $m$ líneas contiene una cadena hexadecimal de longitud 64 y un entero no negativo $k_i$, que representan la cadena final recibida por Bob en la comunicación $i$ y su umbral de ruido.

Para obligarte a responder en línea, después de convertir la cadena hexadecimal en una cadena binaria de 256 bits, debes aplicar XOR a cada uno de sus bits con $lastans$ para obtener la verdadera cadena recibida por Bob. Aquí $lastans\in\{0,1\}$ es la respuesta a la consulta anterior, y su valor inicial antes de la primera consulta es $0$.

Atención: al leer o escribir variables de tipo unsigned long long mediante scanf y printf, el especificador correspondiente es llu.

Salida

Escribe la salida en el archivo qi.out.

La salida contiene $m$ líneas, cada una con un entero $0$ o $1$ que representa la respuesta a la consulta actual.

Ejemplo de consultas

Para facilitar la explicación, presentamos un caso simplificado: damos directamente las palabras del diccionario, reducimos su longitud a 4 y permitimos responder a las consultas fuera de línea.

Considera un diccionario de tamaño $n=2$, con las palabras 1010 y 0111.

Para la consulta B = 1011, con $k_1=1$, la respuesta es $1$: se obtiene invirtiendo el cuarto bit de 1010 (contando desde el más significativo al menos significativo, como en lo que sigue).

Para la consulta 1 = 0001, con $k_2=2$, la respuesta es $1$: se obtiene invirtiendo los bits segundo y tercero de 0111.

Para la consulta 1 = 0001, con $k_3=1$, la respuesta es $0$.

• Al invertir como máximo 1 bit de 1010, se pueden obtener 1010, 0010, 1110, 1000, 1011.
• Al invertir como máximo 1 bit de 0111, se pueden obtener 0111, 1111, 0011, 0101, 0110.
• No se puede obtener 1 = 0001, por lo que necesariamente procede de una interferencia de Eve.

Ejemplos

Ejemplo 1

Consulta los archivos qi/qi1.in y qi/qi1.ans del directorio del concursante.

Ejemplo 2

Consulta los archivos qi/qi2.in y qi/qi2.ans del directorio del concursante.

Ejemplo 3

Consulta los archivos qi/qi3.in y qi/qi3.ans del directorio del concursante.

Restricciones

Para todos los casos de prueba: $1\le n\le 4\times 10^5$, $1\le m\le 1.2\times 10^5$, $0\le k\le 15$. Los valores de $a_1,a_2$ se generan uniformemente al azar en $[0,2^{64}-1]$.