给定 $K$，构造两个长度最多为 $8848$ 的非空 01 字符串 $S$ 和 $T$，使得它们恰好有 $K$ 个不同的最长公共子序列。更正式地，如果 $L$ 是 $S$ 和 $T$ 的最长公共子序列的长度，则应恰好存在 $K$ 个不同的长度为 $L$ 的 01 字符串，它们同时是 $S$ 和 $T$ 的子序列。

在题目的限制下，保证这样的字符串总是存在。

输入格式

输入仅包含一行，一个整数 $K$ ($1 \le K \le 10^9$)。

输出格式

在两行中分别输出非空 01 字符串 $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。

让字符串的长度超过珠穆朗玛峰（8848）是不礼貌的……