Victor's arch-nemesis, Roger, has taken control of the weather in Canada! He threatens it with acid rain, to take revenge against the citizens of DMOJistan who have plagued him with questions about art class.

Victor has researched a solution to counter Roger's rage-induced attack. Victor has cultivated a tree that can absorb the acid rain without harming the environment. Now all Victor has to do is get the trees in position for Roger's attacks.

Roger, wanting the citizens of DMOJistan to witness the carnage, has announced his attack plan. He has prepared $N$ raindrops that will fall at various lattice points at specific times. Unfortunately, in his rage, he forgot to account for the second dimension, so his one-dimensional attack will only hit points along the $x$-axis.

It's expensive to create trees to absorb Roger's rage-induced attack, so Victor wants to prepare as few trees as possible to absorb all of the acid rain. After preparing each of the trees, Victor can arrange for them to be moved to other locations. A tree can be moved at most one unit per second. All trees can move independently and trees can be in the same location at any point in time. Victor is able to put trees anywhere starting at time zero.

Help Victor compute the minimum number of trees he needs to prepare, and also determine which tree will be used to absorb each attack.

Constraints

$N\le {10}^5$

$0\le x_i,t_i\le {10}^9$

All $(x_i,t_i)$ are distinct.

For at most 20% of full credit, $N\le 85$ and at most four trees will be required.

For at most 60% of full credit, $N\le 8\cdot {10}^3$.

Input Specification

The first line will contain a single integer, $N$.

Each of the next $N$ lines will contain two integers, $x_i$ and $t_i$, indicating that Roger will attack $(x_i,0)$ at time $t_i$ with acid rain.

Output Specification

Print $N+1$ lines. The first line will contain an integer $T$, the minimum number of trees that Victor will need to prepare.

Afterwards, on each of the following $N$ lines, print an integer $k$ between $1$ and $T$, indicating that tree $k$ will be used to absorb the attack described by the matching line in the input.

If there are multiple ways to assign trees to absorb the attacks, print any.

Sample Input

5
1 1
2 3
1 5
3 4
2 6

Sample Output

2
1
1
2
1
2