You are the leader of a tower-rushing squad, and you must lead your subordinates to carry out a firm and comprehensive tower rush.
There are $n$ towers on a plane, where the $i$-th tower is located at $(x_i, y_i)$, and all positions are distinct. You can choose any number of towers to rush, provided that the following two conditions are met:
- To ensure the safe return of your subordinates, at most two towers can be rushed for any given x-coordinate, and at most two towers can be rushed for any given y-coordinate.
- To ensure the comprehensiveness of the rush, any tower that is not rushed must be "sandwiched" between two towers with the same x-coordinate that have already been rushed, or between two towers with the same y-coordinate that have already been rushed.
Construct a valid tower-rushing plan, or determine that no solution exists.
Input
The first line contains a positive integer $n$.
The next $n$ lines each contain two integers $x_i, y_i$.
Output
If no solution exists, output $-1$.
Otherwise, output a binary string of length $n$, where the $i$-th character is $1$ if and only if you choose to rush the $i$-th tower.
Examples
Input 1
3 1 1 1 6 1 5
Output 1
110
Note 1
For each x-coordinate and y-coordinate, at most two towers are rushed, and the only tower that is not rushed is sandwiched between two towers with the same x-coordinate.
Input 2
6 1 1 1 2 2 1 2 2 3 1 3 2
Output 2
110011
Input 3
See the provided files.
Output 3
See the provided files.
Constraints
This problem uses bundled testing.
For all data, it is guaranteed that $1 \le x_i, y_i, n \le 10^6$.
| Subtask ID | $n \le$ | Special Properties | Score |
|---|---|---|---|
| $1$ | $3$ | $5$ | |
| $2$ | $16$ | $11$ | |
| $3$ | $10^6$ | There exist $a, b$ such that $n=ab$, and $1 \le x_i \le b, 1 \le y_i \le a$. | $7$ |
| $4$ | $10^6$ | At most two towers on each x-coordinate. | $6$ |
| $5$ | $5000$ | $31$ | |
| $6$ | $10^5$ | $21$ | |
| $7$ | $10^6$ | $19$ |