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

As time passes, the bacteria multiply and expand their territory simultaneously in the shape of squares, all expanding at the same rate. Specifically, for any time $t$ and any point $p$ on the plane, if there is a bacterium of type $i$ at point $p$, the following two conditions apply:

• If every square centered at point $p$ contains bacteria of other types, the bacteria at that point will not expand (this can be called "contact inhibition").
• If there exists a square centered at point $p$ that does not contain bacteria of other types, the bacteria at that point will expand.

Note that the expanded bacteria of the same type also possess the same expansion capability.

Here are some simple examples of square expansion:

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

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

Now, for each type $i$ of bacterium, determine whether its occupied area can tend to infinity.

Input

The first line contains a positive integer $n$ ($1 \le n \le 10^6$), representing the number of initial bacteria.

The next $n$ lines each contain two integers, representing the coordinates $(x_i, y_i)$ of the point, which is the location of the initial bacterium of type $i$.

Output

Output a binary string of length $n$. For the $i$-th digit, $1$ indicates that the occupied area of the bacterium of type $i$ can expand to infinity, and $0$ indicates that the final area is finite.

Examples

Input 1

5
0 0
2 0
2 2
0 2
1 1

Output 1

11110

Input 2

3
-2 0
0 0
2 0

Output 2

111

Input 3

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

Output 3

1101110

Note

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

Constraints

For 25% of the data, $n \le 10^2$. For 50% of the data, $n \le 10^3$. For 75% of the data, $n \le 10^5$. For 100% of the data, $n \le 10^6$, $-10^9 \le x_i, y_i \le 10^9$.