시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB46548.889%

문제

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$.

서브태스크

번호배점제한
15

$N ≤ 3$

211

$N ≤ 16$

37

$N = ab$ for some positive integers $a$, $b$ and $(X_{ai+j} , Y_{ai+j}) = (i + 1, j)$ for all integers $i$, $j$ with $0 ≤ i ≤ b - 1$, $1 ≤ j ≤ a$

46

For every integer $a$, there are at most two cities whose $x$-coordinate is $a$.

531

$N ≤ 5000$

621

$N ≤ 100000$

719

-

예제 입력 1

3
1 1
1 6
1 5

예제 출력 1

110

If we build towers in cities $1$ and $2$ which have the same $x$-coordinate, city $3$ which also has the same $x$-coordinate lies on the line segment between them.

An example of an incorrect output would be $111$, as there will be more than two towers having $x$-coordinate equal to $1$ if towers are built in all $3$ cities.

Another incorrect output is $101$, as even though city $2$ shares the same $y$-coordinate with cities $1$ and $3$, it does not lie on the line segment between them.

This testcase is valid for subtasks 1, 2, 5, 6, and 7.

예제 입력 2

6
1 1
1 2
2 1
2 2
3 1
3 2

예제 출력 2

110011

City $3$ lies on the line segment between cities $1$ and $5$ which have the same $y$-coordinate, and city $4$ lies on the line segment between cities $2$ and $6$ which have the same $y$-coordinate.

This testcase is valid for subtasks 2, 3, 4, 5, 6, and 7.

예제 입력 3

8
1 13
2 13
7 27
7 13
7 2
2 27
7 4
4 13

예제 출력 3

10101101

This testcase is valid for subtasks 2, 5, 6, and 7.

채점 및 기타 정보

  • 예제는 채점하지 않는다.