El equipo "Lyuboyn" — el niño pequeño Askhat, el niño mediano Sanzhar y el niño grande Nurbakyt — han decidido ampliar sus conocimientos y estudiar un poco de electrónica. Se les ocurrió un extraño interruptor electromecánico que modifica la señal analógica que recibe de una manera especial. Contentos con su invención, la llamaron orgullosamente "El interruptor Lyuboyn".

Para ser precisos, una señal puede representarse como una secuencia de $N$ bits, y "El interruptor Lyuboyn" es tal que la señal de salida que produce difiere de la entrada en exactamente $K$ bits y ninguna señal de entrada produce la misma señal de salida. Para hacer su invención aún más magnífica, los chicos añadieron la característica final: si el parámetro binario $T$ se establece en 1, la secuencia vinculada de salidas será cíclica, es decir, si comienzas con una señal, la reemplazas con su salida del interruptor y repites el procedimiento suficientes veces, en algún momento volverás a la señal con la que empezaste originalmente. Esto, sin embargo, no será cierto si el parámetro $T$ se establece en 0.

En esta tarea, se te pide repetir el logro del equipo y generar "El código Lyuboyn" — el mapeo de señales de salida a señales de entrada dadas que produce el interruptor. Para facilitar las cosas, solo necesitas imprimir la secuencia vinculada de salidas como se describió anteriormente, comenzando con una señal $S$.

Formalmente, necesitas encontrar una secuencia $f$ de longitud $2^N$ que consista en números binarios de longitud $N$ (incluyendo ceros a la izquierda), tal que:

1. $f_0 = S$
2. Para todo $i$ y $j$ ($i \neq j$), $f_i \neq f_j$
3. Para cualquier $i$ ($0 \le i < 2^N - 1$), $f_i$ difiere de $f_{i+1}$ en exactamente $K$ dígitos en su representación binaria. Además, si el parámetro $T$ es igual a 1, entonces la secuencia debe ser cíclica, es decir, $f_{2^N - 1}$ también debe diferir de $f_0$ en exactamente $K$ dígitos en su representación binaria.

Entrada

La primera línea de la entrada contiene tres números enteros $N$, $K$ y $T$ ($2 \le N \le 18$, $1 \le K < N$, $0 \le T \le 1$).

La segunda línea contiene la representación binaria del número inicial $S$.

Salida

Si no existe tal secuencia, imprime una sola línea que contenga -1.

De lo contrario, la primera línea de la salida debe contener el número de valores en la secuencia vinculada — $2^N$.

Las líneas numeradas de 2 a $2^N + 2$ deben contener un solo número binario cada una — el valor de $f_{i-2}$.

Si hay múltiples soluciones válidas, puedes imprimir cualquiera de ellas.

Subtareas

Esta tarea contiene ocho subtareas:

1. Prueba de ejemplo. 0 puntos.
2. $N = 4, K = 3, T = 1, S = 0$. 5 puntos.
3. $2 \le N \le 18$, $K$ es par, $T \le 1$, $S < 2^N$. 3 puntos.
4. $2 \le N \le 18$, $K = 1, T = 1, S = 0$. 11 puntos.
5. $2 \le N \le 18$, $K = 3, T = 0, S = 0$. 15 puntos.
6. $2 \le N \le 18$, $K \cdot 2 < N, T = 0, S < 2^N$. 18 puntos.
7. $2 \le N \le 18$, $K < N, T = 0, S < 2^N$. 31 puntos.
8. $2 \le N \le 18$, $K < N, T = 1, S < 2^N$. Restricciones originales. 17 puntos.

Ejemplos

Entrada 1

2 1 1
10

Salida 1

4
10
11
01
00