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