Bit Pattern (MTS)

For each position, flag whether its value appears at an earlier position and whether it appears at a later position, and return two binary strings. The current position itself does not count as an occurrence.

输入格式

The first line contains n, followed by n integers. 1≤n≤10000, 0≤num[i]≤10000; the catalog mistakenly merged a line break into 10^40.

输出格式

The first line holds the earlier-occurrence flags and the second line the later-occurrence flags; each line has exactly n digits.

样例 1

输入：

5
1 2 1 3 2

输出：

00101
11000

样例 2

输入：

1
0

输出：

0
0

样例 3

输入：

3
7 7 7

输出：

011
110

样例说明

Example 1 gives 00101 and 11000; a single element gives 0 on both lines; three 7s give 011 and 110.