Dla danego $K$ skonstruuj dwa niepuste słowa binarne $S$ i $T$, każde o długości co najwyżej $8848$, mające dokładnie $K$ różnych najdłuższych wspólnych podciągów. Formalnie, jeśli $L$ jest długością najdłuższego wspólnego podciągu $S$ i $T$, powinno istnieć dokładnie $K$ różnych słów binarnych długości $L$ będących podciągami zarówno $S$, jak i $T$.

Zagwarantowano, że przy ograniczeniach tego zadania takie słowa zawsze istnieją.

Wejście

Jedyny wiersz wejścia zawiera jedną liczbę całkowitą $K$ ($1\le K\le 10^9$).

Wyjście

Wypisz niepuste słowa binarne $S$ i $T$ w osobnych wierszach. Długość każdego z nich nie powinna przekraczać $8848$. Mogą mieć różne długości.

Jeśli istnieje więcej niż jedno rozwiązanie, możesz wypisać dowolne z nich.

Przykład

Wejście 1

1

Wyjście 1

1111
00

Wejście 2

2

Wyjście 2

10
01

Wejście 3

3

Wyjście 3

010
1001

Wejście 4

100

Wyjście 4

10001000001011100001010100011
11000010001010101001010011100

Uwagi

W pierwszym przykładzie najdłuższy wspólny podciąg 1111 i 00 ma długość $0$, a istnieje tylko jedno słowo długości $0$, które jest podciągiem obu — słowo puste.

W drugim przykładzie długość najdłuższego wspólnego podciągu słów 10 i 01 wynosi $1$, a istnieją $2$ słowa długości $1$ będące podciągami zarówno $S$, jak i $T$: 0 i 1.

W drugim przykładzie długość najdłuższego wspólnego podciągu słów 010 i 1001 wynosi $2$, a istnieją $3$ słowa długości $2$ będące podciągami zarówno $S$, jak i $T$: 00, 01 i 10.

Tworzenie słów dłuższych niż Everest byłoby brakiem szacunku…