Étant donné $K$, construisez deux chaînes binaires non vides $S$ et $T$, chacune de longueur au plus $8848$, qui possèdent exactement $K$ sous-séquences communes les plus longues distinctes. Plus formellement, si $L$ est la longueur de la plus longue sous-séquence commune à $S$ et $T$, il doit exister exactement $K$ chaînes binaires distinctes de longueur $L$ qui soient des sous-séquences à la fois de $S$ et de $T$.

Il est garanti que, sous les contraintes de ce problème, de telles chaînes existent toujours.

Entrée

L'unique ligne de l'entrée contient un entier $K$ ($1\le K\le 10^9$).

Sortie

Affichez les chaînes binaires non vides $S$ et $T$ sur des lignes séparées. La longueur de chacune ne doit pas dépasser $8848$. Elles peuvent avoir des longueurs différentes.

S'il existe plusieurs solutions, vous pouvez afficher n'importe laquelle.

Exemples

Entrée 1

1

Sortie 1

1111
00

Entrée 2

2

Sortie 2

10
01

Entrée 3

3

Sortie 3

010
1001

Entrée 4

100

Sortie 4

10001000001011100001010100011
11000010001010101001010011100

Remarque

Dans le premier exemple, la plus longue sous-séquence commune de 1111 et 00 a une longueur de $0$, et il n'existe qu'une seule chaîne de longueur $0$ qui soit une sous-séquence des deux : la chaîne vide.

Dans le deuxième exemple, la longueur de la plus longue sous-séquence commune des chaînes 10 et 01 est $1$, et il existe $2$ chaînes de longueur $1$ qui sont des sous-séquences à la fois de $S$ et de $T$ : 0 et 1.

Dans le deuxième exemple, la longueur de la plus longue sous-séquence commune des chaînes 010 et 1001 est $2$, et il existe $3$ chaînes de longueur $2$ qui sont des sous-séquences à la fois de $S$ et de $T$ : 00, 01 et 10.

Il serait irrespectueux de créer des chaînes plus longues que l'Everest…