题目描述

今天有 $N$ 个项目会被发布。Jongyoung 和他的朋友们不想做太多工作，于是决定把这些项目分给大家完成。

第 $i$ 个项目可以从时间 $L_i$ 开始获取，并且必须在时间 $R_i$ 或更早完成。由于大家学习能力有限，一旦某个学生选择了一个项目，就会占用该项目对应的整个时间区间。

同一个学生不能同时处理多个项目。因此，如果某个学生选择了项目 $i$ 和项目 $j$，必须满足：

或者

此外，大家都不想承担太多工作，所以每个学生最多处理两个项目。

现在有 $M$ 名能力较强的学生，希望他们总共完成尽可能多的项目。请你为每个项目决定由哪名学生负责；如果某个项目不被完成，则输出 $0$。

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

输入格式

第一行包含两个整数 $N,M$，分别表示项目数量和学生数量。

接下来 $N$ 行，每行包含两个整数 $L_i,R_i$，表示第 $i$ 个项目的开始时间和截止时间。

输出格式

输出 $N$ 个整数。

第 $i$ 个整数表示负责第 $i$ 个项目的学生编号，编号范围为 $1$ 到 $M$。如果第 $i$ 个项目没有被完成，则输出 $0$。

输出方案中被完成的项目数量必须达到最大可能值。

数据范围

• $1\le M\le N\le 3\cdot 10^5$；
• $1\le L_i<R_i\le 10^9$。

样例 1

输入

7 5
9 10
7 9
3 4
9 10
2 6
8 9
5 8

输出

3 2 2 5 5 4 1

样例 2

输入

2 2
1 2
3 4

输出

1 1

样例 3

输入

2 1
1 2
2 3

输出

1 0

样例说明

样例输出只展示了一种可能的最优分配方案。若有多种完成项目数相同且最大的方案，输出任意一种均可。