시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 1024 MB5615950.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
W3sicHJvYmxlbV9pZCI6IjIwNTYxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2ZjXHVjODFjIFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNjI0XHViMjk4IFx1YzFhMVx1YzhmZFx1ZDU1OVx1YzBhY1x1YzVkMCAkTiRcdWFjMWNcdWM3NTggXHVhY2ZjXHVjODFjXHVhYzAwIFx1YzYyY1x1Yjc3Y1x1YzYyYyBcdWM2MDhcdWM4MTVcdWM3NzRcdWIyZTQuIFx1Yzg4NVx1YzYwMVx1Yzc3NFx1YzY0MCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NDAgXHVhZGY4XHViMmU0XHVjOWMwIFx1YWNmY1x1YzgxY1x1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjMmY2XHVjOWMwIFx1YzU0YVx1YzczY1x1YmJjMFx1Yjg1YyBcdWFjZmNcdWM4MWNcdWI0ZTRcdWM3NDQgXHViZDg0XHViMmY0XHVkNTc0XHVjMTFjIFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmY1x1YzgxYyAkaSRcdWIyOTQgXHVjMmRjXHVhYzAxICRMX2kkXHVjNWQwIFx1YzYyY1x1Yjc3Y1x1YzY0MCBcdWMyZGNcdWFjMDEgJFJfaSRcdWFlNGNcdWM5YzAgXHVjODFjXHVjZDljXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWQ1NTlcdWMyYjVcdWIyYTVcdWI4MjVcdWM3NzQgXHVhZGY4XHViMmU0XHVjOWMwIFx1YjZmMFx1YzViNFx1YjA5OFx1YzljMCBcdWM1NGFcdWM1NDQgXHVjODFjXHVjZDljXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWMyZGNcdWFjMDQgXHViMGI0XHViMGI0IFx1YWRmOCBcdWFjZmNcdWM4MWNcdWI5N2MgXHVkNTc0XHVhY2IwXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwIFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YjQ1MCBcdWFjZmNcdWM4MWNcdWI5N2MgXHVkNTc0XHVhY2IwXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWM3M2NcdWJiYzBcdWI4NWMgXHViNDUwIFx1YWNmY1x1YzgxYyAkaSRcdWM2NDAgJGokXHViOTdjIFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVkNTc0XHVhY2IwXHVkNTU4XHViODI0XHViYTc0ICRSX2kgJmx0OyBMX2okIFx1YjYxMFx1YjI5NCAkUl9qICZsdDsgTF9pJFx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YWNmY1x1YzgxY1x1YzVkMCBcdWFkZjhcdWIyZTRcdWM5YzAgXHVkMDcwIFx1YWQwMFx1YzJlY1x1Yzc3NCBcdWM1YzZcdWM3M2NcdWJiYzBcdWI4NWMgXHVkNTVjIFx1ZDU1OVx1YzBkZFx1YjJmOSBcdWNkNWNcdWIzMDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWFjZmNcdWM4MWNcdWI5N2MgXHVkNTc0XHVhY2IwXHVkNTYwIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JE0kXHViYTg1XHVjNzU4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YWNmY1x1YzgxY1x1Yjk3YyBcdWQ1NzRcdWFjYjBcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTYwIFx1YjU0YywgXHVkNTU5XHVjMGRkXHViNGU0IFx1YWMwMVx1YWMwMVx1Yzc3NCBcdWQ1NzRcdWFjYjBcdWQ1NzRcdWM1N2MgXHVkNTYwIFx1YWNmY1x1YzgxY1x1Yjk3YyBcdWM4MTVcdWQ1NzRcdWM4ZmNcdWM3OTAuIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWVjXHViN2ZmIFx1Yzc4OFx1Yzc0NCBcdWFjYmRcdWM2YjAgXHVjNWI0XHViNWE0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWM1ZWNcdWIzYzQgXHVjODhiXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggJE4kXHVhY2ZjICRNJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlcSBNIFxcbGVxIE4gXFxsZXEgMzAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0ICROJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzgxNVx1YzIxOCAkTF9pJFx1YzY0MCAkUl9pJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlcSBMX2kgJmx0OyBSX2kgXFxsZXEgMTBeOSkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+JE4kXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gJGkkXHViYzg4XHVjOWY4IFx1YzIxOFx1Yjg1Y1x1YjI5NCBcdWFjZmNcdWM4MWMgJGkkXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU2MCBcdWQ1NTlcdWMwZGRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjZmNcdWM4MWMgJGkkXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU2MCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0IFx1YjMwMFx1YzJlMCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMDU2MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Iktub3dsZWRnZSBJcy4uLiIsImRlc2NyaXB0aW9uIjoiPHA+VG9kYXksICROJCBwcm9qZWN0cyBhcmUgc2NoZWR1bGVkIHRvIGJlIHBvc3RlZCBhdCBTb25nanVrIEhha3NhLiBKb25neW91bmcgYW5kIGhpcyBmcmllbmRzIGRvbiYjMzk7dCB3YW50IHRvIGRvIGEgbG90IG9mIHdvcmssIHNvIHRoZXkgZGVjaWRlZCB0byBzaGFyZSB0aGUgcHJvamVjdHMgYW5kIGltcGxlbWVudCB0aGVtLjxcL3A+XHJcblxyXG48cD5UaGUgcHJvamVjdCAkaSQgY2FuIGJlIGFjY2Vzc2VkIGF0IHRpbWUgJExfaSQgYW5kIHNoYWxsIGJlIGltcGxlbWVudGVkIGF0IHRpbWUgJFJfaSQgb3IgZWFybGllciwgYnV0IHRoZSBzdHVkZW50cyYjMzk7IGxlYXJuaW5nIGFiaWxpdHkgaXMgbm90IHZlcnkgZ29vZCwgc28gd29yayBvbiB0aGUgcHJvamVjdCBjb25zdW1lcyBhbGwgdGhlIGF2YWlsYWJsZSB0aW1lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBhZGRpdGlvbiwgYSBzdHVkZW50IGNhbm5vdCBzb2x2ZSBzZXZlcmFsIHByb2plY3RzIGF0IHRoZSBzYW1lIHRpbWUsIHNvIGlmIGEgc3R1ZGVudCBzZWxlY3RlZCB0d28gcHJvamVjdHMgJGkkIGFuZCAkaiQsICRSX2kgJmx0OyBMX2okIG9yICRSX2ogJmx0OyBMX2kkIG11c3QgYmUgc2F0aXNmaWVkLiBBbHNvLCBzdHVkZW50cyBhcmUgbm90IHZlcnkgaW50ZXJlc3RlZCBpbiBoYXJkIHdvcmssIHNvIGVhY2ggc3R1ZGVudCB3aWxsIHdvcmsgb24gYSBtYXhpbXVtIG9mIHR3byBwcm9qZWN0cy48XC9wPlxyXG5cclxuPHA+QSBncm91cCBvZiAkTSQgc3Ryb25nIHN0dWRlbnRzIHdhbnQgdG8gY29sbGVjdGl2ZWx5IGltcGxlbWVudCBhcyBtYW55IHByb2plY3RzIGFzIHBvc3NpYmxlLiBIZWxwIHRoZW0gZGVjaWRlIHdoaWNoIHByb2plY3RzIGVhY2ggc3R1ZGVudCBuZWVkcyB0byBzb2x2ZS4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIHBvc3NpYmxlIHdheXMsIHlvdSBtYXkgY2hvb3NlIGFueSBvbmUgb2YgdGhlbS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkTiQgYW5kICRNJCwgdGhlIG51bWJlciBvZiBwcm9qZWN0cyBhbmQgdGhlIG51bWJlciBvZiBzdHVkZW50cywgcmVzcGVjdGl2ZWx5ICgkMSBcXGxlcSBNIFxcbGVxIE4gXFxsZXEgMyBcXGNkb3QgMTBeNSQpLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgJE4kIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkTF9pJCBhbmQgJFJfaSQ6IHRoZSBzdGFydCBhbmQgZW5kIHRpbWUgb2YgJGkkLXRoIHByb2plY3QgKCQxIFxcbGVxIExfaSAmbHQ7IFJfaSBcXGxlcSAxMF45JCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgJE4kIGludGVnZXJzLiBUaGUgJGkkLXRoIG9mIHRob3NlIGludGVnZXJzIG11c3QgYmUgdGhlIG51bWJlciBvZiBzdHVkZW50IChmcm9tICQxJCB0byAkTSQpIHdobyB3aWxsIGhhbmRsZSBwcm9qZWN0ICRpJC4gSWYgbm8gc3R1ZGVudCB3aWxsIGRvIHByb2plY3QgJGkkLCBvdXRwdXQgJDAkIGluc3RlYWQuPFwvcD5cclxuXHJcbjxwPlRoZSBudW1iZXIgb2YgaW1wbGVtZW50ZWQgcHJvamVjdHMgbXVzdCBiZSB0aGUgbWF4aW11bSBwb3NzaWJsZS4gSWYgdGhlcmUgYXJlIHNldmVyYWwgcG9zc2libGUgc29sdXRpb25zLCBwcmludCBvbmUgYW55IG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==