Problem Description

In a Cartesian coordinate system (an infinite two-dimensional plane), there are $n$ bacteria of different species, each located at distinct coordinates.

As time progresses, the bacteria continuously reproduce, expanding their territories in the shape of squares at the same rate.

Specifically, for any moment $t$ and any point $p$ on the plane, if point $p$ contains bacteria of the $i$-th species, there are two scenarios:

• If any square centered at point $p$ contains bacteria of other species, the bacteria at that point will not expand (referred to as "contact inhibition").

• If there exists a square centered at $p$ that does not contain bacteria of other species, the bacteria at that point will expand.

Note that the bacteria that expand also have the same expansion capability.

Here are some simple examples of square expansion:

If initially, there is only one bacterium at $(0, 0)$, after one unit of time, this species of bacteria will occupy the square formed by $(1, 1), (1, -1), (-1, -1), (-1, 1)$.

If initially, there are two bacteria at $(0, 0)$ and $(1, 0)$, eventually $(0.5, 0)$ will become the boundary of their territories. The bacterium initially at $(0, 0)$ will occupy the entire area to the left of $(0.5, 0)$, and the bacterium at $(1, 0)$ will occupy the entire area to the right of $(0.5, 0)$.

Now, for the $i$-th species of bacteria, inquire whether its occupied area can expand infinitely.

Input Format

The first line contains a positive integer $n(1 \leq n \leq 10^6)$, representing the number of bacterial colonies.

The next $n$ lines each contain two integers, representing the coordinates $(x_i, y_i)$ of the bacterial colony of species $i$.

Output Format

Output a string of length $n$ consisting of '0's and '1's. For the $i$-th character, '1' indicates that the occupied area of the $i$-th species of bacteria can expand infinitely, and '0' indicates that the final area is finite.

Sample Input and Output

Sample Input #1

5
0 0
2 0
2 2
0 2
1 1

Sample Output #1

11110

Sample Input #2

3
-2 0
0 0
2 0

Sample Output #2

111

Sample Input #3

7
-7 -8
5 -9
1 -5
9 -4
-8 3
-2 -3
-4 -6

Sample Output #3

1101110

Notes

[Sample Explanation]

In the second sample, the point $(0, 0)$ will eventually occupy the area between the lines $x = -1$ and $x = 1$, with an area that tends to infinity.

[Data Range]

For $25\%$ of the data, $n \leq 10^2$.

For $50\%$ of the data, $n \leq 10^3$.

For $75\%$ of the data, $n \leq 10^5$.

For $100\%$ of the data, $1 \leq n \leq 10^6$, $-10^9 \leq x_i, y_i \leq 10^9$.

见题面 Input 部分

见题面 Output 部分