給定 $K$，構造兩個長度至多為 $8848$ 的非空二進位字串 $S$ 和 $T$，使它們恰好有 $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 還長可是很不敬的……