408083: GYM102979 K Knowledge Is...

Today, $$$N$$$ projects are scheduled to be posted at Songjuk Haksa. Jongyoung and his friends don't want to do a lot of work, so they decided to share the projects and implement them.

The project $$$i$$$ can be accessed at time $$$L_i$$$ and shall be implemented at time $$$R_i$$$ or earlier, but the students' learning ability is not very good, so work on the project consumes all the available time.

In addition, a student cannot solve several projects at the same time, so if a student selected two projects $$$i$$$ and $$$j$$$, $$$R_i < L_j$$$ or $$$R_j < L_i$$$ must be satisfied. Also, students are not very interested in hard work, so each student will work on a maximum of two projects.

A group of $$$M$$$ strong students want to collectively implement as many projects as possible. Help them decide which projects each student needs to solve. If there are multiple possible ways, you may choose any one of them.

The first line of input contains two integers $$$N$$$ and $$$M$$$, the number of projects and the number of students, respectively ($$$1 \leq M \leq N \leq 3 \cdot 10^5$$$).

Each of the following $$$N$$$ lines contains two integers $$$L_i$$$ and $$$R_i$$$: the start and end time of $$$i$$$-th project ($$$1 \leq L_i < R_i \leq 10^9$$$).

Print $$$N$$$ integers. The $$$i$$$-th of those integers must be the number of student (from $$$1$$$ to $$$M$$$) who will handle project $$$i$$$. If no student will do project $$$i$$$, output $$$0$$$ instead.

The number of implemented projects must be the maximum possible. If there are several possible solutions, print one any of them.

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
1 2
3 4

1 1 

2 1
1 2
2 3

1 0