苹果园被表示为一条一维直线。共有 $N$ 个苹果，第 $i$ 个苹果在时间 $t_i$ 落于位置 $x_i$。

机器人移动的最大速度为 $1$。为了接住第 $i$ 个苹果，机器人必须在时间 $t_i$ 恰好位于位置 $x_i$。每个机器人可以从任意位置出发，在接住最后一个苹果后也可以停在任意位置。

你的任务是使用尽可能少的机器人接住所有苹果。你还需要输出每个苹果分别由哪个机器人接住。

输入格式

第一行包含一个整数 $N$ ($1 \leq N \leq 2 \cdot 10^5$)，表示苹果的数量。

接下来的 $N$ 行，每行包含两个整数 $t_i$ 和 $x_i$ ($1 \leq t_i, x_i \leq 10^9$)，分别表示第 $i$ 个苹果落下的时间和位置。

所有数对 $(t_i, x_i)$ 均不相同。

输出格式

输出一个整数 $K$，表示接住所有苹果所需的最少机器人数量。

在下一行输出 $N$ 个整数 $a_1, a_2, \dots, a_N$，其中 $a_i$ 是接住第 $i$ 个苹果的机器人编号。

编号必须在 $1$ 到 $K$ 之间，且 $1$ 到 $K$ 之间的每个编号都必须至少被使用一次。

如果存在多种最优分配方案，输出其中任意一种即可。

仅对于第 4 组测试点，允许只输出整数 $K$。

子任务

你的解法将在多组测试数据上进行测试。 要获得某一组的分数，你必须通过该组中的所有测试用例。

样例

样例输入 1

4
1 1
3 2
5 3
8 1

样例输出 1

1
1 1 1 1

样例输入 2

3
1 1
2 5
3 1

样例输出 2

2
1 2 1

样例输入 3

4
2 2
3 1
3 3
4 2

样例输出 3

2
1 1 2 1

说明

在第一个样例中，一个机器人可以按顺序接住所有苹果。

在第二个样例中，苹果 $1$ 和 $3$ 可以由同一个机器人接住，但苹果 $2$ 必须由另一个机器人接住。

在第三个样例中，最少需要 $2$ 个机器人，但存在多种不同的最优分配方案。