Towers

Benson the Rabbit likes towers. There are $N$ cities numbered $1$ to $N$, and city $i$ is located at the point with integer coordinates $(X_i, Y_i)$. No two cities are located at the same point. Benson wants to build towers in some of these cities so that the following conditions hold.

• For any $a$, at most two towers have $x$-coordinate equal to $a$.
• For any $b$, at most two towers have $y$-coordinate equal to $b$.
• Each of the $N$ cities either has a tower, or lies on the line segment between two towers with the same $x$-coordinate or the same $y$-coordinate. More formally, if city $(x, y)$ has no tower, then there are towers at $(x, c)$ and $(x, d)$ with $c \le y \le d$, or towers at $(e, y)$ and $(f, y)$ with $e \le x \le f$.

The first line contains one integer $N$, the number of cities.

The next $N$ lines are such that the $i$-th line contains two integers $X_i$ and $Y_i$, meaning city $i$ is located at the point $(X_i, Y_i)$.

Output one line containing a string of $N$ characters $A_1A_2 \cdots A_N$. $A_i$ is $1$ if Benson builds a tower in city $i$, and $0$ otherwise. The towers built must satisfy all the conditions.

If there are several solutions, your program can output any one of them.

• $1 \le N \le 10^6$
• $1 \le X_i, Y_i \le 10^6$
• For all $i \ne j$, either $X_i \ne X_j$ or $Y_i \ne Y_j$.