Many LCS#13023

Many LCS

4 seconds
256 megabytes
Very hard

Given , construct two non-empty binary strings and of length at most 8848 such that they have exactly different longest common subsequences. More formally, if is the length of the longest common subsequence of and , there should exist exactly distinct binary strings of length which are subsequences of both and .

It is guaranteed that under the constraints of this problem such strings always exist.

Input

The only line of input contains a single integer (1 \le K \le 10^9).

Output

Print non-empty binary strings and on separate lines. The length of each of them should not exceed . They can have different lengths.

If there is more than one solution, you can print any one of them.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading

Note

In the first example, the longest common subsequence of 1111 and 00 has length , and there exists only one string of length which is a subsequence of both of them — the empty string.

In the second example, the length of the longest common subsequence of strings 10 and 01 is , and there are strings of length which are subsequences of both and : 0 and 1.

In the second example, the length of the longest common subsequence of strings 010 and 1001 is , and there are strings of length which are subsequences of both and : 00, 01, and 10.

It would be disrespectful to make strings longer than Everest...