Movie Fan
Contest: Kotlin Heroes: Episode 3
Tags: *special, data structures, greedy, implementation, sortings

Recently, Polycarp has been a fan of cinema novelties and is trying not to miss them!

In the near future, $$$n$$$ new movies will be released: the $$$i$$$-th of them will be airing from the day $$$a_i$$$ and to the day $$$b_i$$$. This means that if Polycarp wants to watch the $$$i$$$-th movie in the cinema, he must do so in the period from $$$a_i$$$ to $$$b_i$$$ inclusive.

If perhaps Polycarp will not have the opportunity to watch a movie in a cinema, he can then do it after day $$$b_i$$$ by watching it using an online service. Of course, this is an undesirable outcome for Polycarp because the whole world will have time to discuss this movie on social networks!

Polycarp can watch no more than $$$m$$$ movies per day. Help Polycarp find a movie-watching schedule such that every movie will be watched in the cinema. If such a schedule does not exist, then Polycarp wants to watch movies so that:

- for each movie that he doesn't have time to watch in the cinema, we will find the number of days between the end of its airing and the day when Polycarpus watches the movie,
- the maximum of the values from the previous point should be as small as possible.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. The following are descriptions of the $$$t$$$ test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — the number of movies and the maximum number of movies that Polycarp can view per day.

In the next $$$n$$$ lines, the movies themselves are described, one per line, by a pair of integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$) — the first and last airing days for the $$$i$$$-th movie.

It is guaranteed that the sum of the values $$$n$$$ for all test cases in the input does not exceed $$$2 \cdot 10^5$$$.

Output format:
Print $$$t$$$ answers to given test cases in the order in which they appear in the input: the $$$i$$$-th answer should consist of two lines. Print the integer $$$d$$$ in the first line of each test case answer:

- $$$d=0$$$, if there is a schedule such that all movies are watched during airing,
- $$$d>0$$$, if such a schedule does not exist — in this case, $$$d$$$ is equal to the minimum value of maximum among all the watching "delays" after the end of airing.

In the second line of the answer to each test case, print $$$n$$$ positive integers $$$t_1, t_2, \dots, t_n$$$, where $$$t_i$$$ is the number of the day when Polycarp needs to watch the $$$i$$$-th movie in the optimal schedule.

If there are several answers, print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
3
7 2
1 2
1 3
2 2
2 3
1 1
2 3
1 2
5 3
1 1
1 1
1 1
1 1
1 1
6 1
13 13
31 31
25 25
12 12
14 14
10 10

Example output:
1
1 3 2 3 1 4 2 
1
1 1 1 2 2 
0
13 31 25 12 14 10

Editorial:
The key observation is the following: when we choose which movies to watch, it's optimal to choose ones whose $$$b_i$$$ are minimal possible. It can be proven by contradiction: suppose we have the answer where $$$t_i > t_j$$$ but $$$b_i < b_j$$$, let's swap $$$t_i$$$ and $$$t_j$$$ and get $$$\max(b_i - t_j, b_j - t_i) \le \max(b_i - t_i, b_j - t_j)$$$ — the contradiction.
Now, let's carefully simulate the process. Let's iterate over day $$$D$$$ and maintain a set of segments $$$[a_i, b_i]$$$ (where $$$a_i \le D$$$) sorted by $$$b_i$$$. The moments of starting airing $$$a_i$$$ will become events.
So we can do the following: for a fixed $$$D$$$, at first, let's add to the set all segments $$$[a_i, b_i]$$$ with $$$a_i = D$$$. Then choose $$$\min(m, \text{set size})$$$ movies we will watch at day $$$D$$$. And finally, if the set is not empty then move from $$$D$$$ to $$$D + 1$$$. Otherwise, let's move $$$D$$$ straight to the next event.
Since there are $$$O(n)$$$ events and $$$O(n)$$$ movies it can be proven that we will check only $$$O(n)$$$ days and there will be $$$O(n)$$$ "first()" and "remove()" queries to the set. So, the total complexity is $$$O(n \log(n))$$$.