Dado $K$, construa duas cadeias binárias não vazias $S$ e $T$, cada uma de comprimento no máximo $8848$, que tenham exatamente $K$ subsequências comuns mais longas distintas. Mais formalmente, se $L$ for o comprimento da subsequência comum mais longa de $S$ e $T$, devem existir exatamente $K$ cadeias binárias distintas de comprimento $L$ que sejam subsequências tanto de $S$ quanto de $T$.

É garantido que, sob as restrições deste problema, tais cadeias sempre existem.

Entrada

A única linha da entrada contém um inteiro $K$ ($1\le K\le 10^9$).

Saída

Imprima as cadeias binárias não vazias $S$ e $T$ em linhas separadas. O comprimento de cada uma não deve exceder $8848$. Elas podem ter comprimentos diferentes.

Se houver mais de uma solução, você pode imprimir qualquer uma delas.

Exemplos

Entrada 1

1

Saída 1

1111
00

Entrada 2

2

Saída 2

10
01

Entrada 3

3

Saída 3

010
1001

Entrada 4

100

Saída 4

10001000001011100001010100011
11000010001010101001010011100

Nota

No primeiro exemplo, a subsequência comum mais longa de 1111 e 00 tem comprimento $0$, e existe apenas uma cadeia de comprimento $0$ que é subsequência de ambas: a cadeia vazia.

No segundo exemplo, o comprimento da subsequência comum mais longa das cadeias 10 e 01 é $1$, e há $2$ cadeias de comprimento $1$ que são subsequências tanto de $S$ quanto de $T$: 0 e 1.

No segundo exemplo, o comprimento da subsequência comum mais longa das cadeias 010 e 1001 é $2$, e há $3$ cadeias de comprimento $2$ que são subsequências tanto de $S$ quanto de $T$: 00, 01 e 10.

Seria desrespeitoso criar cadeias mais longas que o Everest…