CF378B 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$）晋级。

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.