Semifinals

Description:

Input:

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.

Output:

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

Sample Input:

4
9840 9920
9860 9980
9930 10020
10040 10090

Sample Output:

1110
1100

Sample Input:

4
9900 9850
9940 9930
10000 10020
10060 10110

Sample Output:

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.

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