露露, 花花 y 萱萱 se han interesado recientemente por los números aleatorios de los ordenadores. Como es bien sabido, las secuencias de números aleatorios generadas por ordenador no son verdaderamente aleatorias, sino seudoaleatorias, producidas mediante determinadas reglas.

Un día, 露露 conoció un método para generar números aleatorios llamado Mersenne twister. Dados los parámetros iniciales $m\in\mathbb Z^+$, $x\in\mathbb Z\cap[0,2^m)$ y el valor inicial $M_0\in\mathbb Z\cap[0,2^m)$, construye la secuencia seudoaleatoria $\{M_n\}$ mediante la recurrencia:

$$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}$$

Aquí, $\mathrm{xor}$ es la operación de disyunción exclusiva binaria (el operador ^ de C/C++). Se dice que el parámetro $x$ es bueno si, al tender la longitud de la secuencia a infinito, sus valores en $\mathbb Z\cap(0,2^m)$ aparecen aproximadamente con igual probabilidad. Por ejemplo, cuando $m>1$, es evidente que $x=0$ no es bueno.

Después de que 露露 presentara Mersenne twister a sus compañeros, 花花 quiso comprobar su grado de aleatoriedad mediante algunas pruebas clásicas. Para ello, calculó algunos valores $M_k$ con el ordenador.

Pero la atenta 萱萱 observó que, al introducir una vez $k$ en binario, 花花 había añadido por error $l$ ceros al final. Iba a advertirle del descuido, pero 花花 ya había calculado y anotado el valor erróneo de $M_k$ sin guardar el valor de $k$. Aunque en realidad no era un problema grave, cuando 萱萱 le explicó el descuido, 花花, perfeccionista como es, le rogó que corrigiera el valor de $M_k$. 萱萱 te ha encargado esta tarea a ti, su inteligencia artificial.

Entrada

La primera línea del archivo de entrada random.in contiene un entero positivo $m$. La segunda contiene $x$ en binario ($m$ cifras, ordenadas de la menos significativa a la más significativa). La tercera contiene $M_0$ en binario, con el mismo orden que $x$. La cuarta contiene un entero $type$.

A continuación se da uno de estos dos casos:

1. $type=0$ (萱萱 anotó la entrada de 花花): la quinta línea contiene un entero que representa el valor correcto de $k$ anotado por 萱萱.
2. $type=1$ (萱萱 no pudo anotar la entrada de 花花): la quinta línea contiene $l$ y la sexta contiene la representación binaria del valor erróneo de $M_k$ calculado por 花花.

Salida

El archivo de salida random.out debe contener una única línea con una cadena de $m$ ceros y unos que represente el valor correcto de $M_k$ obtenido, también ordenada de la cifra menos significativa a la más significativa.

Ejemplos

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

Salida 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

Salida 2

0101111001

Entrada y salida 3

Consulta random/random.in y random/random.ans en el directorio del concursante.

Restricciones