Semifinals

## 题目描述 在跑步比赛中，两场半决赛刚刚结束。每场半决赛有 $n$ 名选手参加。一共有 $n$ 名选手能够晋级决赛。晋级规则如下：对于每场半决赛，前 $k$（$0 \le 2 k \le n$）名选手能够直接晋级决赛；对于其余选手，前 $n − 2 k$ 名选手晋级决赛。 现在 $k$ 还没有公布，每名选手都想知道他能否晋级。 **【输入格式】** 第一行一个整数 $n$（$1 \le n \le {10}^5$），表示每场半决赛的人数。 接下来 $n$ 行，每行两个整数 $a_i, b_i$（$1 \le a_i, b_i \le {10}^9$），表示两组半决赛中第 $i$ 名选手的成绩（跑的时间）。所有成绩保证各不相同，且 $a_1, a_2, \ldots, a_n$ 和 $b_1, b_2, \ldots, b_n$ 均为升序。 **【输出格式】** 输出共两行，均为长度为 $n$ 的 $01$ 串，代表两组半决赛的选手是否能晋级。其中第一行对应 $a$ 数组的选手，第二行对应 $b$ 数组的选手。 每一行的第 $i$ 个字符如果为 `1`，表示这一组的第 $i$ 名有机会晋级，如果为 `0`，表示他没有机会晋级。 **【样例解释】** 第一组半决赛每名选手的成绩分别为 9840, 9860, 9930, 10040 第二组半决赛每名选手成绩为 9920, 9980, 10020, 10090。 当 $k=0$ 时，成绩为 $9840, 9860, 9920, 9930$ 的选手晋级 当 $k=1$ 时，每组第一名（$9840$ 和 $9920$）晋级，其余选手中 $9860$ 和 $9930$ 晋级。 当 $k=2$ 时，每组前两名（$9840, 9860$ 和 $9920$，$9980$）晋级。

Two semifinals have just been in the running tournament. Each semifinal had $ n $ participants. There are $ n $ participants advancing to the finals, they are chosen as follows: from each semifinal, we choose $ k $ people ( $ 0<=2k<=n $ ) who showed the best result in their semifinals and all other places in the finals go to the people who haven't ranked in the top $ k $ in their semifinal but got to the $ n-2k $ of the best among the others. The tournament organizers hasn't yet determined the $ k $ value, so the participants want to know who else has any chance to get to the finals and who can go home.

The first line contains a single integer $ n $ ( $ 1<=n<=10^{5} $ ) — the number of participants in each semifinal. Each of the next $ n $ lines contains two integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i},b_{i}<=10^{9} $ ) — the results of the $ i $ -th participant (the number of milliseconds he needs to cover the semifinals distance) of the first and second semifinals, correspondingly. All results are distinct. Sequences $ a_{1} $ , $ a_{2} $ , ..., $ a_{n} $ and $ b_{1} $ , $ b_{2} $ , ..., $ b_{n} $ are sorted in ascending order, i.e. in the order the participants finished in the corresponding semifinal.

Print two strings consisting of $ n $ characters, each equals either "0" or "1". The first line should correspond to the participants of the first semifinal, the second line should correspond to the participants of the second semifinal. The $ i $ -th character in the $ j $ -th line should equal "1" if the $ i $ -th participant of the $ j $ -th semifinal has any chances to advance to the finals, otherwise it should equal a "0".

4
9840 9920
9860 9980
9930 10020
10040 10090

1110
1100

4
9900 9850
9940 9930
10000 10020
10060 10110

1100
1100

Consider the first sample. Each semifinal has 4 participants. The results of the first semifinal are 9840, 9860, 9930, 10040. The results of the second semifinal are 9920, 9980, 10020, 10090. - If $ k=0 $ , the finalists are determined by the time only, so players 9840, 9860, 9920 and 9930 advance to the finals. - If $ k=1 $ , the winners from both semifinals move to the finals (with results 9840 and 9920), and the other places are determined by the time (these places go to the sportsmen who run the distance in 9860 and 9930 milliseconds). - If $ k=2 $ , then first and second places advance from each seminfial, these are participants with results 9840, 9860, 9920 and 9980 milliseconds.