CF378B.Semifinals

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 ≤ 2_k_ ≤ 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 - 2_k_ 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.

两场半决赛刚刚结束。每场半决赛各有 $n$ 名参赛者。共有 $n$ 名参赛者晋级决赛，其选拔规则如下：从每场半决赛中，选出成绩最好的 $k$ 人（其中 $0 \leq 2k \leq n$）直接晋级；其余 $n - 2k$ 个决赛名额，则分配给那些未进入各自半决赛前 $k$ 名，但在所有未直接晋级者中成绩最好的前 $n - 2k$ 人。

目前，赛事组织方尚未确定参数 $k$ 的取值，因此参赛者希望了解：哪些人仍有晋级决赛的可能，而哪些人已确定无法晋级、可以离场回家。

The first line contains a single integer n (1 ≤ n ≤ 105) — 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 ≤ 109) — 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.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 每场半决赛的参赛人数。

接下来的 $n$ 行中，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq 10^9$）—— 分别表示第 $i$ 位参赛者在第一场和第二场半决赛中的成绩（单位：毫秒）。所有成绩互不相同。序列 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_n$ 均按升序排列，即按各场半决赛中参赛者的完赛顺序给出。

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".

输出两个长度为 $n$ 的字符串，每个字符均为 "0" 或 "1"。第一行对应第一场半决赛的参赛者，第二行对应第二场半决赛的参赛者。第 $j$ 行中的第 $i$ 个字符应为 "1"，当且仅当第 $j$ 场半决赛中的第 $i$ 位参赛者仍有晋级决赛的可能；否则该字符应为 "0"。

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.

考虑第一个样例。每个半决赛有 4 名参赛者。第一个半决赛的成绩为：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 毫秒的选手晋级决赛。