Amazin’ Inc 是一家新兴的电子商务公司，最近优化了其运营流程，以充分利用其员工。得益于最先进的预测方法，Amazin’ 现在可以提前获知未来一段时间内每天所需的员工人数。利用这些信息，他们可以每天通过解雇和/或招聘员工来调整劳动力规模，从而确保每天的员工人数恰好满足需求。为了防止员工过于安逸并组织起来，他们还会定期解雇员工并用新人替换。例如，如果某天比前一天多需要 4 名员工，Amazin’ 可能会解雇 10 人，然后在那一天招聘 14 名新人。

不幸的是，根据劳动法，解雇员工必须遵循后进先出（LIFO）的原则：入职时间最短的员工必须最先被解雇。此外，被解雇的人在可预见的未来内不能被重新聘用，因此无法通过解雇一些人然后立即重新聘用其中部分人的方式来规避法律。

但这个故事实际上是关于人力资源（HR）部门的，而不是员工！每天，HR 部门会指派一名员工负责向被解雇的员工传达解雇的坏消息，并向新招聘的员工传达入职的好消息。为了最大限度地减少 HR 员工之间因社交尴尬而产生的工作环境问题，公司制定了一项政策，要求负责解雇某位员工的 HR 必须与当初招聘该员工时负责接待的 HR 是不同的人。

现在，HR 部门也需要进行优化，尽可能精简人员。与普通员工不同，新的 HR 员工无法在短时间内招聘，因此 HR 人员必须是长期雇员。为了管理所有计划中的招聘和解雇工作，最少需要多少名 HR 人员？

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示可预见未来的天数。接下来的 $n$ 行，第 $i$ 行包含两个整数 $f_i$ 和 $h_i$ ($0 \le f_i, h_i \le 10^6$)，其中 $f_i$ 是第 $i$ 天解雇的员工人数，$h_i$ 是招聘的员工人数。

每天解雇的员工人数永远不会超过当前在职的员工人数（换句话说，对于所有 $1 \le i \le n$，满足 $f_i \le \sum_{j=0}^{i-1} h_j - \sum_{j=1}^{i-1} f_j$）。

输出格式

输出一行，包含一个整数 $k$，表示所需的最少 HR 人员数量。HR 人员的 ID 任意指定为 $1$ 到 $k$。然后输出一行，包含 $n$ 个整数，其中第 $i$ 个整数表示负责第 $i$ 天解雇和招聘工作的 HR 人员的 ID。如果存在多种方案，输出任意一种即可。

样例

样例输入 1

4
0 3
1 1
2 1
2 0

样例输出 1

3
1 2 3 2

样例输入 2

6
0 10
0 5
2 0
0 0
0 100
50 100

样例输出 2

2
1 2 1 2 1 2