CF1297F.Movie Fan

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.

最近，Polycarp 成为了电影新片的忠实粉丝，努力不错过任何一部！

在不久的将来，将上映 $n$ 部新电影：其中第 $i$ 部电影将在第 $a_i$ 天至第 $b_i$ 天（含）期间在影院放映。这意味着，若 Polycarp 想在影院观看第 $i$ 部电影，则必须在 $a_i$ 到 $b_i$ 这一时间段内完成观看。

如果 Polycarp 未能在影院观看某部电影，他之后仍可在第 $b_i$ 天之后通过在线流媒体服务观看该片。当然，这对 Polycarp 来说是一种不理想的结果，因为此时全世界早已在社交媒体上热议完这部电影了！

Polycarp 每天最多可观看 $m$ 部电影。请帮助 Polycarp 制定一个观影计划，使得每部电影都能在影院内被观看。若这样的计划不存在，则 Polycarp 希望安排观影计划，使得：

• 对于每一部他无法在影院观看的电影，我们计算其放映结束日（即 $b_i$）与 Polycarp 实际观看该片之日之间的天数差；
• 上述所有天数差中的最大值尽可能小。

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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 输入中测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$，$1 \le m \le 10^9$）—— 分别表示电影的数量以及 Polycarp 每天最多可观看的电影数量。

接下来的 $n$ 行中，每行描述一部电影，由一对整数 $a_i$、$b_i$（$1 \le a_i \le b_i \le 10^9$）给出—— 分别表示第 $i$ 部电影的首播日和末播日。

保证输入中所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

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 \gt 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.

按输入中测试用例出现的顺序，输出 $t$ 个测试用例的答案：第 $i$ 个答案应包含两行。在每个测试用例答案的第一行中，输出整数 $d$：

• 若存在一种安排方案使得所有电影均能在其播出期间被观看，则 $d = 0$；
• 若不存在这样的安排方案，则 $d > 0$；此时，$d$ 等于所有观看“延迟”（即观看时间与电影播出结束时刻之差）的最大值的最小可能值。

在每个测试用例答案的第二行中，输出 $n$ 个正整数 $t_1, t_2, \dots, t_n$，其中 $t_i$ 表示 Polycarp 在最优安排下观看第 $i$ 部电影的日期编号。

若存在多个可行答案，输出任意一个即可。