시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 1024 MB 34 6 4 100.000%

문제

오늘 송죽학사에 $N$개의 과제가 올라올 예정이다. 종영이와 친구들은 그다지 과제를 하고 싶지 않으므로 과제들을 분담해서 해결하기로 했다.

과제 $i$는 시각 $L_i$에 올라와 시각 $R_i$까지 제출할 수 있는데, 학생들의 학습능력이 그다지 뛰어나지 않아 제출이 가능한 시간 내내 그 과제를 해결해야 한다. 또 한 학생이 동시에 두 과제를 해결할 수 없으므로 두 과제 $i$와 $j$를 한 학생이 해결하려면 $R_i < L_j$ 또는 $R_j < L_i$를 만족해야 한다. 또 학생들은 과제에 그다지 큰 관심이 없으므로 한 학생당 최대 두 개의 과제를 해결할 것이다.

$M$명의 학생이 최대한 많은 과제를 해결하고자 할 때, 학생들 각각이 해결해야 할 과제를 정해주자. 가능한 경우가 여럿 있을 경우 어떤 방법을 선택하여도 좋다.

입력

첫 줄에 정수 $N$과 $M$이 주어진다. $(1 \leq M \leq N \leq 300\,000)$

이후 $N$개의 줄에 걸쳐 정수 $L_i$와 $R_i$가 주어진다. $(1 \leq L_i < R_i \leq 10^9)$

출력

$N$개의 수를 공백으로 구분하여 출력한다. $i$번째 수로는 과제 $i$를 해결할 학생을 출력한다. 과제 $i$를 해결할 학생이 없다면 대신 0을 출력한다.

예제 입력 1

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

예제 출력 1

3 2 2 5 5 4 1

예제 입력 2

2 2
1 2
3 4

예제 출력 2

1 1

예제 입력 3

2 1
1 2
2 3

예제 출력 3

1 0

출처

High School > 경기과학고등학교 > 나는코더다 2020 송년대회 J번