За заданим $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 було б неповагою…