Cansado de calcular respostas a problemas estranhos módulo $998244353$ ou $10^9+7$, 小 E criou um enigma relacionado com $2$:

Dada uma grelha com $2$ linhas e $2^k$ colunas, deve preencher as suas $2^{k+1}$ células com os inteiros de $1$ a $2^{k+1}$, sem repetições nem omissões, respeitando as seguintes restrições de comparação entre células adjacentes.

Concretamente, são dadas três sequências binárias $a,b,c$, de comprimentos $2^k-1$, $2^k$ e $2^k-1$, respetivamente. Uma matriz $A$ de dimensão $2\times2^k$ é uma solução do enigma se, e somente se, satisfizer simultaneamente as quatro condições seguintes:

1. $A$ contém cada inteiro de $1,2,\ldots,2^{k+1}$ exatamente uma vez.
2. Para todo $1\le i<2^k$, tem-se $a_i=[A_{1,i}<A_{1,i+1}]$.
3. Para todo $1\le i\le2^k$, tem-se $b_i=[A_{1,i}<A_{2,i}]$.
4. Para todo $1\le i<2^k$, tem-se $c_i=[A_{2,i}<A_{2,i+1}]$.

Aqui, $[P]$ vale $1$ se a condição $P$ for verdadeira, e $0$ caso contrário.

Para si, encontrar uma solução qualquer ou determinar que não existe solução seria demasiado fácil. Como este é um enigma sobre $2$, 小 E pede-lhe que calcule o número de soluções módulo $2$.

小 E preparou $t$ enigmas com grelhas do mesmo tamanho e comprimiu-os em conjunto de forma eficiente. Para cada enigma, deve calcular o número de soluções módulo $2$.

Detalhes de implementação

Não precisa de implementar a função main, nem deve fazê-lo.

O programa submetido deve incluir o ficheiro de cabeçalho puzzle.h, adicionando o código seguinte no início do programa:

#include "puzzle.h"

Deve implementar a função seguinte no ficheiro de código-fonte submetido:

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

• $t,k$ representam, respetivamente, o número de enigmas e o tamanho da grelha.
• Para $0\le i<2^k-1$, o bit $j$ da representação binária de $a_i$ ($0\le j<t$) indica a restrição de comparação entre $A_{1,i+1}$ e $A_{1,i+2}$ no enigma $j+1$.
• Para $0\le i<2^k$, o bit $j$ da representação binária de $b_i$ ($0\le j<t$) indica a restrição de comparação entre $A_{1,i+1}$ e $A_{2,i+1}$ no enigma $j+1$.
• Para $0\le i<2^k-1$, o bit $j$ da representação binária de $c_i$ ($0\le j<t$) indica a restrição de comparação entre $A_{2,i+1}$ e $A_{2,i+2}$ no enigma $j+1$.
• A função deve devolver um inteiro não negativo cujo bit $j$ da representação binária ($0\le j<t$) seja o número de soluções do enigma $j+1$ módulo $2$.
• Para cada caso de teste, a biblioteca chama esta função exatamente uma vez.

Atenção: em quaisquer circunstâncias, a biblioteca demora no máximo 0.1 segundos a executar e utiliza uma quantidade fixa de memória, que não excede 64 MiB.

Como testar o programa

O ficheiro grader.cpp no diretório do problema é uma implementação de referência da biblioteca. A biblioteca usada na avaliação final tem uma implementação diferente, pelo que a sua solução não deve depender da implementação da biblioteca.

Pode compilar o executável no diretório do problema com o seguinte comando:

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

Para o executável compilado:

• O executável lê da entrada padrão dados no seguinte formato:

  • A primeira linha contém dois inteiros positivos $t,k$, que representam o número de enigmas e o tamanho da grelha, respetivamente.
  • A linha $3i-1$ ($1\le i\le t$) contém uma cadeia binária $a_1\ldots a_{2^k-1}$ de comprimento $2^k-1$.
  • A linha $3i$ ($1\le i\le t$) contém uma cadeia binária $b_1\ldots b_{2^k}$ de comprimento $2^k$.
  • A linha $3i+1$ ($1\le i\le t$) contém uma cadeia binária $c_1\ldots c_{2^k-1}$ de comprimento $2^k-1$.

• O executável escreve na saída padrão dados no seguinte formato:

  • A saída tem $t$ linhas. A linha $i$ ($1\le i\le t$) contém um inteiro não negativo que representa o número de soluções do enigma $i$ módulo $2$.

Exemplos

Entrada 1

2 1
1
01
1
1
00
1

Saída 1

1
0

Entrada 2

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

Saída 2

1
1
0
0

Descrição dos ficheiros anexos

Nos ficheiros anexos:

1. grader.cpp é a implementação de referência da biblioteca fornecida.
2. puzzle.h é o ficheiro de cabeçalho; não precisa de se preocupar com o seu conteúdo.
3. template_puzzle.cpp é o código de exemplo fornecido, que pode consultar para implementar o seu próprio código.

Subtarefas

Para todos os dados de teste:

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

Propriedade especial A: $t\le4$.

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

Pontuação

Atenção:

• Não deve obter informações internas da biblioteca por meios ilegais, como interagir diretamente com os fluxos de entrada e saída padrão. Esse comportamento será considerado batota.
• A implementação da biblioteca de avaliação final difere da biblioteca de exemplo.

Este problema está sujeito, em primeiro lugar, às mesmas restrições que um problema tradicional. Por exemplo, um erro de compilação resulta em 0 pontos para todo o problema; erros de execução ou ultrapassar os limites de tempo ou memória resultam em 0 pontos no caso de teste correspondente. O programa só pode aceder às variáveis que definir e às fornecidas pela biblioteca. Tentar aceder a outros espaços de endereços poderá provocar erros de compilação ou de execução.

Além das condições acima:

• Em cada caso de teste, o programa recebe a pontuação máxima se, e somente se, a resposta devolvida pela chamada à função puzzle estiver correta.