Given $n$ horizontal line segments and $n$ vertical line segments on a plane, it is guaranteed that no two segments lie on the same line.

Two segments are connected if they intersect. If $a$ and $b$ are connected, and $b$ and $c$ are connected, then $a$ and $c$ are connected.

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

Input

The first line contains an integer $n$.

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

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

Output

Output two lines, each being a binary 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, and $0$ otherwise.

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

Examples

Input 1

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

Output 1

0100010000
1001000010

Subtasks

For $100\%$ of the data, $2 \le n \le 10^5$.