Problem Description

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 Format

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 Format

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

4
1 1
3 2
5 3
8 1

1
1 1 1 1

3
1 1
2 5
3 1

2
1 2 1

4
2 2
3 1
3 3
4 2

2
1 1 2 1

Hint

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.

Explanation of Sample

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.