Dado $K$, construye dos cadenas binarias no vacías $S$ y $T$, cada una de longitud como máximo $8848$, tales que tengan exactamente $K$ subsecuencias comunes más largas distintas. Más formalmente, si $L$ es la longitud de la subsecuencia común más larga de $S$ y $T$, debe haber exactamente $K$ cadenas binarias distintas de longitud $L$ que sean subsecuencias tanto de $S$ como de $T$.

Se garantiza que, bajo las restricciones de este problema, tales cadenas siempre existen.

Entrada

La única línea de la entrada contiene un entero $K$ ($1\le K\le 10^9$).

Salida

Imprime las cadenas binarias no vacías $S$ y $T$ en líneas separadas. La longitud de cada una no debe superar $8848$. Pueden tener longitudes distintas.

Si hay más de una solución, puedes imprimir cualquiera de ellas.

Ejemplos

Entrada 1

1

Salida 1

1111
00

Entrada 2

2

Salida 2

10
01

Entrada 3

3

Salida 3

010
1001

Entrada 4

100

Salida 4

10001000001011100001010100011
11000010001010101001010011100

Nota

En el primer ejemplo, la subsecuencia común más larga de 1111 y 00 tiene longitud $0$, y solo existe una cadena de longitud $0$ que sea subsecuencia de ambas: la cadena vacía.

En el segundo ejemplo, la longitud de la subsecuencia común más larga de las cadenas 10 y 01 es $1$, y hay $2$ cadenas de longitud $1$ que son subsecuencias tanto de $S$ como de $T$: 0 y 1.

En el segundo ejemplo, la longitud de la subsecuencia común más larga de las cadenas 010 y 1001 es $2$, y hay $3$ cadenas de longitud $2$ que son subsecuencias tanto de $S$ como de $T$: 00, 01 y 10.

Sería una falta de respeto crear cadenas más largas que el Everest…