Problem Description

Now, on the Cartesian coordinate system (an infinitely large 2D plane), there are $n$ bacteria of different types, and their coordinates are all distinct.

As time goes on, the bacteria keep reproducing. They expand their territory in the shape of squares, all with the same square expansion speed.

More specifically, for any time $t$ and any point $p$ on the plane, suppose there exists type $i$ bacteria at point $p$. Then there are two cases:

• If every square centered at point $p$ contains bacteria of other types, then the bacteria at this point will not expand (this can be called “contact inhibition”).

• If there exists a square centered at $p$ that contains no bacteria of other types, then the bacteria at this point will expand.

Note that newly expanded bacteria of the same type also have the same expansion ability.

Here are some simple examples of square expansion:

If initially there is only one bacterium at $(0, 0)$ on the plane, then after one unit of time, this type of bacteria will occupy the square surrounded by $(1, 1)$, $(1, -1)$, $(-1, -1)$, $(-1, 1)$.

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

Now, for the $i$-th type of bacteria, you need to determine whether its occupied area can grow to infinity.

Input Format

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

Then follow $n$ lines, each containing two integers, representing the point coordinates $(x_i, y_i)$, i.e., the position of the mother of type $i$ bacteria.

Output Format

Output a $01$ string of length $n$. For the $i$-th character, $1$ means the occupied area of type $i$ bacteria can expand to infinity, and $0$ means the final area is finite.

5
0 0
2 0
2 2
0 2
1 1

11110

3
-2 0
0 0
2 0

111

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

1101110

Hint

Sample Explanation

In the second sample, the territory finally owned by point $(0, 0)$ is the region between the lines $x = -1$ and $x = 1$, and its area tends to infinity.

Constraints

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

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

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

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

Translated by ChatGPT 5