B. Bitstring Accruing Policy Convergence
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

For a bitstring $$$s$$$ (meaning $$$s$$$ consists of 0s and 1s), we define $$$f(s)$$$ as the string obtained by replacing each 0 in $$$s$$$ with 001, and each 1 with 01. For example, $$$f(\texttt{001}) = \texttt{00100101}$$$, and $$$f(\texttt{111}) = \texttt{010101}$$$.

We write $$$f^x(s)$$$ to denote applying $$$f$$$ to some string $$$x$$$ times. For example, $$$f^5(s)$$$ means $$$f(f(f(f(f(s)))))$$$.

You are given a list of $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$. You need to find bitstrings $$$s$$$ and $$$t$$$ that satisfy all the following conditions:

  • $$$s$$$ and $$$t$$$ have the same length.
  • The length of $$$s$$$ and $$$t$$$ is between $$$1$$$ and $$$3 \cdot 10^5$$$ inclusive.
  • $$$s$$$ and $$$t$$$ contain the same number of 0s, and the same number of 1s.
  • Let $$$S = f^{22}(s)$$$ and $$$T = f^{22}(t)$$$. Then, $$$a$$$ is exactly the list of indices where $$$S$$$ and $$$T$$$ are different. Or more formally: for all $$$1 \leq j \leq |S|$$$, we have $$$S_j \neq T_j$$$ if and only if $$$j$$$ is an element of $$$a$$$.

Note that this last condition implies that all values $$$a_i$$$ must be less than or equal to the length of $$$S$$$ and $$$T$$$.

We guarantee that a solution exists in all tests. If there are multiple solutions, you can output any of them.

Input

The first line contains $$$n$$$, the number of positions ($$$2 \leq n \leq 3 \cdot 10^5$$$).

The next $$$n$$$ lines contain integers $$$a_1, a_2, \ldots, a_n$$$, the positions ($$$1 \leq a_i \leq 10^{18}$$$).

it is guaranteed that all positions are distinct, and that a solution exists.

Output

Output $$$s$$$ and $$$t$$$ satisfying the conditions above, on two separate lines.

If there are multiple solutions, you can output any of them.

Examples
Input
2
1134903170
1134903171
Output
10
01
Input
4
1134903170
2269806340
1134903171
2269806341
Output
110
011
Input
6
1134903170
1134903171
2269806340
2269806341
4106118243
4106118244
Output
1100001
0101001
Input
8
12318354730
16424472972
2971215074
10482042826
2971215073
10482042827
16424472973
12318354729
Output
0101111100110
0011111001101
Note

Why the magic number $$$22$$$ in the problem statement? Maybe one of the organizers is a Taylor Swift fan (guess who).

In the first test, $$$s$$$ and $$$t$$$ differ by exactly two positions. $$$f(s) = \texttt{01001}$$$ and $$$f(t)=\texttt{00101}$$$, which also differ by exactly two positions. In fact, we can show that for all positive integers $$$n$$$, $$$f^n(s)$$$ and $$$f^n(t)$$$ differ by exactly two positions.

In the second test, note that solutions such as $$$s=\texttt{011}$$$ and $$$t=\texttt{110}$$$ would also be accepted.

In the third test, note that solutions such as $$$s=\texttt{1100}$$$ and $$$t=\texttt{0101}$$$ would also be accepted.