Problem Description

On a plane, you are given $n$ horizontal line segments and $n$ vertical line segments. It is guaranteed that no two different segments lie on the same straight line.

If two segments have an intersection point, then they are connected. If $a, b$ are connected and $b, c$ are connected, then $a, c$ are connected.

A segment $a$ is critical if and only if there exist two other segments $b, c$ such that $b, c$ are connected, and after deleting $a$, $b, c$ are no longer connected.

Input Format

The first line contains an integer $n$.

The next $n$ lines: the $i$-th line contains two integers $l, r$ ($1 \le l < r \le n$), representing a horizontal segment with $l \le x \le r$ and $y=i$.

The next $n$ lines: the $i$-th line contains two integers $d, u$ ($1 \le d < u \le n$), representing a vertical segment with $x = i$ and $d \le y \le u$.

Output Format

Output two lines, each being a $01$ string of length $n$.

The $i$-th character of the first line is $1$ if and only if the $i$-th horizontal segment is critical.

The $i$-th character of the second line is $1$ if and only if the $i$-th vertical segment is critical.

10
1 4
2 7
1 6
3 7
2 4
1 9
1 3
9 10
3 5
1 7
1 7
1 3
1 3
3 7
1 2
3 5
1 7
5 7
3 9
9 10

0100010000
1001000010

Hint

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078&nzhtl1477

Constraints: for $100\%$ of the testdata, $2 \le n \le 10^5$.

Translated by ChatGPT 5