小Z está a estudar por conta própria temas relacionados com computadores quânticos. Recentemente, ao estudar o capítulo sobre comunicação quântica, encontrou um problema interessante. Neste problema, Alice e Bob comunicam por meios quânticos, usando como linguagem um dicionário $S$ de tamanho $n$. Cada palavra $s_i$, com $1\le i\le n$, pode ser representada por uma cadeia binária de 256 bits. Neste problema, as palavras $s_i$ podem ser geradas chamando a função gen, que podes consultar em gen.cpp, no diretório do problema. Os parâmetros n, a1 e a2 dessa função são fornecidos na entrada.

Alice e Bob vão realizar $m$ comunicações. Em cada uma, Alice transmite a Bob exatamente uma palavra do dicionário. Porém, o canal que utilizam não é fiável e sofre interferência de ruído. Mais precisamente, na transmissão $i$, seja $x_i$ a palavra original transmitida por Alice. O ruído pode inverter, no máximo, $k_i$ bits dessa cadeia binária. Por outras palavras, se $y_i$ for a cadeia recebida por Bob, pode diferir de $x_i$ em, no máximo, $k_i$ posições, e pode nem sequer pertencer ao dicionário $S$.

Entretanto, Bob descobriu que o malfeitor Eve também se infiltrou no canal e se prepara para interferir nas comunicações. Eve pode substituir a cadeia recebida por Bob por uma cadeia binária arbitrária de 256 bits, que também pode não pertencer a $S$. Eve é muito astuto e não interfere necessariamente em todas as comunicações.

Bob pediu-te ajuda. Para cada uma das próximas comunicações, dadas a cadeia binária que Bob recebe no final e a tolerância ao ruído $k_i$, com $0\le k_i\le15$, determina se é possível que Eve não tenha interferido. Isto equivale a determinar se a cadeia recebida pode ser obtida a partir de alguma palavra do dicionário invertendo, no máximo, $k_i$ bits. Se for possível que Eve não tenha interferido, apresenta $1$; caso contrário, apresenta $0$. Bob confia muito nas tuas capacidades, pelo que tens de responder às consultas em linha, segundo os requisitos específicos da entrada.

Para reduzir o tempo de leitura, as cadeias recebidas por Bob são fornecidas como cadeias hexadecimais de comprimento 64, compostas pelos algarismos 0 a 9 e pelas letras maiúsculas A a F. As letras A a F representam, por ordem, os valores $10$ a $15$. Cada caráter hexadecimal pode ser convertido nos respetivos bits: por exemplo, 5 corresponde a 0101, A a 1010 e C a 1100.

Entrada

Lê os dados do ficheiro qi.in.

A primeira linha contém quatro inteiros não negativos $n,m,a_1,a_2$, que representam, respetivamente, o tamanho do dicionário, o número de comunicações e os valores iniciais dos parâmetros a1 e a2 da função gen.

Deves chamar no teu programa a função gen referida na descrição para gerar o dicionário. Podes copiar e utilizar o código de gen.cpp. A matriz booleana s[N+1][256] desse programa contém todas as palavras.

Seguem-se $m$ linhas, cada uma com uma cadeia hexadecimal de comprimento $64$ e um inteiro não negativo $k_i$, que representam, respetivamente, a cadeia binária que Bob recebe no final da comunicação $i$ e a tolerância ao ruído.

Para obrigar a responder às consultas em linha, depois de converteres a cadeia hexadecimal numa cadeia binária de 256 bits, tens de aplicar o OU exclusivo de cada bit com $lastans$ para obter a verdadeira cadeia recebida por Bob nessa comunicação. Aqui, $lastans\in\{0,1\}$ é a resposta à consulta anterior e tem valor inicial $0$ antes da primeira consulta.

Atenção: ao ler ou escrever variáveis do tipo unsigned long long com as funções scanf e printf, o especificador correspondente é llu.

Saída

Escreve a saída no ficheiro qi.out.

Apresenta $m$ linhas, cada uma com um inteiro $0$ ou $1$, que representa a resposta à consulta atual.

Exemplos de consultas

Para facilitar a explicação, ilustramos uma situação simplificada em que as palavras do dicionário são dadas diretamente, o seu comprimento é reduzido para 4 e é permitido responder às consultas fora de linha.

Considera um dicionário de tamanho $n=2$, com as palavras 1010 e 0111.

Para a consulta B = 1011 com $k_1=1$, a resposta deve ser $1$: obtém-se invertendo o quarto bit de 1010, contando do mais significativo para o menos significativo, como também se fará a seguir.

Para a consulta 1 = 0001 com $k_2=2$, a resposta deve ser $1$: obtém-se invertendo os bits 2 e 3 de 0111.

Para a consulta 1 = 0001 com $k_3=1$, a resposta deve ser $0$.

• Invertendo, no máximo, 1 bit de 1010, podem obter-se 1010, 0010, 1110, 1000 e 1011.
• Invertendo, no máximo, 1 bit de 0111, podem obter-se 0111, 1111, 0011, 0101 e 0110.
• Não se consegue obter 1 = 0001; esta cadeia resulta necessariamente da interferência de Eve.

Exemplos

Exemplo 1

Consulta os ficheiros qi/qi1.in e qi/qi1.ans no diretório dos concorrentes.

Exemplo 2

Consulta os ficheiros qi/qi2.in e qi/qi2.ans no diretório dos concorrentes.

Exemplo 3

Consulta os ficheiros qi/qi3.in e qi/qi3.ans no diretório dos concorrentes.

Restrições dos testes

Para todos os testes: $1\le n\le4\times10^5$, $1\le m\le1.2\times10^5$, $0\le k\le15$. Os valores de $a_1$ e $a_2$ são gerados uniformemente ao acaso no intervalo $[0,2^{64}-1]$.