An apple orchard is represented as a one-dimensional line. There are $N$ apples, and apple $i$ falls at time $t_i$ at position $x_i$.

A robot can move at speed at most $1$. To catch apple $i$, a robot must be exactly at position $x_i$ at time $t_i$. Each robot may start at any position, and after catching its last apple it may end anywhere.

Your task is to catch all apples using as few robots as possible. You must also output which robot catches each apple.

Input

The first line contains one integer $N$ ($1 \leq N \leq 2 \cdot 10^5$), the number of apples.

The following $N$ lines each contain two integers $t_i$ and $x_i$ ($1 \leq t_i, x_i \leq 10^9$), the time and position of apple $i$.

All pairs $(t_i, x_i)$ are distinct.

Output

Print one integer $K$, the minimum number of robots needed to catch all apples.

Then print $N$ integers $a_1, a_2, \dots, a_N$ on the next line, where $a_i$ is the id of the robot that catches apple $i$.

The ids must be between $1$ and $K$, and every id from $1$ to $K$ must be used at least once.

If there are multiple optimal assignments, you may output any of them.

For Group 4 only, it is also allowed to print only the integer $K$.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

Sample Input 1

4
1 1
3 2
5 3
8 1

Sample Output 1

1
1 1 1 1

Sample Input 2

3
1 1
2 5
3 1

Sample Output 2

2
1 2 1

Sample Input 3

4
2 2
3 1
3 3
4 2

Sample Output 3

2
1 1 2 1

Explanation of Samples

In the first sample, one robot can catch every apple in order.

In the second sample, apples $1$ and $3$ can be caught by the same robot, but apple $2$ must be caught by a different robot.

In the third sample, the minimum number of robots is $2$, but there are several different optimal assignments.