露露, 花花 e 萱萱 interessaram-se recentemente pelos números aleatórios nos computadores. Como se sabe, as sequências de números aleatórios geradas por computadores não são verdadeiramente aleatórias: são números pseudoaleatórios gerados segundo determinadas regras.

Um dia, 露露 conheceu um método de geração de números aleatórios chamado Mersenne twister. Dados os parâmetros iniciais $m\in\mathbb Z^+$, $x\in\mathbb Z\cap[0,2^m)$ e o valor inicial $M_0\in\mathbb Z\cap[0,2^m)$, ele constrói a sequência pseudoaleatória $\{M_n\}$ pela seguinte recorrência:

$$M_n=\begin{cases}2M_{n-1},&2M_{n-1}<2^m,\\(2M_{n-1}-2^m)\mathbin{\mathrm{xor}}x,&2M_{n-1}\ge2^m.\end{cases}$$

Aqui, $\mathrm{xor}$ é a operação de ou exclusivo binário (o operador ^ em C/C++). Uma escolha do parâmetro $x$ é considerada boa se, quando o comprimento da sequência tende a infinito, os seus valores em $\mathbb Z\cap(0,2^m)$ aparecem com probabilidades aproximadamente iguais. Por exemplo, quando $m>1$, $x=0$ claramente não é uma escolha boa.

Depois de 露露 apresentar o Mersenne twister aos seus amigos, 花花 quis avaliar a sua aleatoriedade com alguns testes clássicos. Para isso, calculou alguns valores de $M_k$ no computador.

Mas 萱萱, atenta, percebeu que, numa ocasião, 花花 introduziu $l$ zeros a mais no final da representação binária de $k$. Ia avisá-lo do engano, mas 花花 já tinha calculado e registado o valor errado de $M_k$, sem registar o valor de $k$. Embora isso não fosse propriamente um problema fatal, quando 萱萱 lhe contou o engano, 花花, perfeccionista, implorou-lhe que ajudasse a corrigir o valor de $M_k$. 萱萱 passou então a tarefa à sua IA: tu.

Entrada

A primeira linha do ficheiro random.in contém um inteiro positivo $m$. A segunda linha contém $x$ em binário: $m$ números, ordenados do bit menos significativo para o mais significativo. A terceira linha contém $M_0$ em binário, na mesma ordem que $x$. A quarta linha contém um inteiro $type$.

A partir daí, há duas possibilidades:

1. $type=0$ (萱萱 registou a entrada de 花花): a quinta linha contém um inteiro, o valor correto de $k$ registado por 萱萱.
2. $type=1$ (萱萱 não conseguiu registar a entrada de 花花): a quinta linha contém $l$ e a sexta contém a representação binária do valor errado de $M_k$ calculado por 花花.

Saída

O ficheiro random.out deve conter uma única linha: uma cadeia de $m$ bits, composta por 0 e 1, que represente o valor correto de $M_k$ calculado por ti, também do bit menos significativo para o mais significativo.

Exemplos

Entrada 1

10
1 1 1 0 0 1 1 1 0 0
1 1 1 0 0 0 0 0 1 1
0
100

Saída 1

0101111001

Entrada 2

10
1 1 1 0 0 1 1 1 0 0
1 1 1 0 0 0 0 0 1 1
1
3
0 1 0 1 1 1 1 1 0 1

Saída 2

0101111001

Exemplo 3

Consulta random/random.in e random/random.ans no diretório dos participantes.

Restrições