По заданному $K$ постройте две непустые двоичные строки $S$ и $T$, каждая длиной не более $8848$, у которых ровно $K$ различных наибольших общих подпоследовательностей. Более формально, если $L$ — длина наибольшей общей подпоследовательности $S$ и $T$, то должно существовать ровно $K$ различных двоичных строк длины $L$, являющихся подпоследовательностями как $S$, так и $T$.

Гарантируется, что при ограничениях этой задачи такие строки всегда существуют.

Входные данные

Единственная строка ввода содержит одно целое число $K$ ($1\le K\le 10^9$).

Выходные данные

Выведите непустые двоичные строки $S$ и $T$ в отдельных строках. Длина каждой из них не должна превышать $8848$. Они могут иметь разные длины.

Если решений несколько, можно вывести любое из них.

Примеры

Входные данные 1

1

Выходные данные 1

1111
00

Входные данные 2

2

Выходные данные 2

10
01

Входные данные 3

3

Выходные данные 3

010
1001

Входные данные 4

100

Выходные данные 4

10001000001011100001010100011
11000010001010101001010011100

Примечание

В первом примере наибольшая общая подпоследовательность строк 1111 и 00 имеет длину $0$, и существует лишь одна строка длины $0$, являющаяся подпоследовательностью обеих строк, — пустая строка.

Во втором примере длина наибольшей общей подпоследовательности строк 10 и 01 равна $1$, и есть $2$ строки длины $1$, являющиеся подпоследовательностями как $S$, так и $T$: 0 и 1.

Во втором примере длина наибольшей общей подпоследовательности строк 010 и 1001 равна $2$, и есть $3$ строки длины $2$, являющиеся подпоследовательностями как $S$, так и $T$: 00, 01 и 10.

Делать строки длиннее Everest было бы неуважительно…