Chengdong的晋级问题

Chengdong的朋友举办了两场ACM比赛，但是他无法判断哪一些人有机会进入总决赛， 所以她找到了Chengdong来解决这个问题

但是Chengdong今天CPU过热了，无法解决这个问题，但是他又不好意思回绝他的朋友，所以他就把这个问题扔给了你们

他们选择的规则如下：

从每个半决赛中，他们会选择在半决赛中表现最好的决赛选手k个（0≤2k≤n），然后在剩下的没有在半决赛中排在前k位的人中在选择最好的n  -  2k个。

但是问题就在于说他们无法确定k，所以他们要求你给你可能进入总决赛人的名单

The first line contains a single integer n (1 ≤ n ≤ 10⁵) — 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⁹) — 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₁, a₂, ..., a_n and b₁, b₂, ..., b_n are sorted in ascending order, i.e. in the order the participants finished in the corresponding semifinal.

第一行包含一个整数n（1≤n≤105） - 每个半决赛中参与者的数量。

接下来的n行中的每一行都包含两个整数ai和bi（1≤ai，bi≤109） - 第一个和第二个半决赛的第i个参与者的结果（解决问题的时间）相应地。所有结果都是不同的。序列a1，a2，...，an和b1，b2，...，bn按照升序排列，即按照参与者在对应的半决赛中完成的顺序。

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个参与者有机会晋级总决赛，那么第j条线上的第i个字符应该等于“1”，否则应该等于“0”。

4
9840 9920
9860 9980
9930 10020
10040 10090

1110
1100

4
9900 9850
9940 9930
10000 10020
10060 10110

1100
1100

 Note

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.
对于第一个例子，每个半决赛有4个参与者。第一个半决赛的结果是9840,9860,9930,10040。第二个半决赛的结果是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. 如果k为0，进入总决赛的人则为他们解决问题的时间决定，则进入的名单为9840,9860,9920和9930
 
 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). 如果k为1，则来自两个半决赛的获胜者移动到决赛（结果9840和9920），剩下的n-2k即2个人则由他们解决问题的时间决定，即9860和9930
 
 If k = 2, then first and second places advance from each seminfial, these are participants with results 9840, 9860, 9920 and 9980 milliseconds. 如果k为2，每次半决赛的前两名进入总决赛，9840,9860,9920和9980