27290번 - Towers 서브태스크스페셜 저지다국어

Benson the Rabbit likes towers. There are $N$ cities numbered $1$ to $N$, and city $i$ is located at a 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 such that the following conditions are satisfied:

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

Benson knows that it is always possible to build towers satisfying these conditions, but does not know how he should do so. Help Benson determine where he should build the towers.

Your program must read from standard input.

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

In the next $N$ lines, the $i$^th line contains two integers $X_i$, $Y_i$, which means city $i$ is located at the point $(X_i , Y_i)$.

Your program must print to standard output.

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

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

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