Movie Fan
Description
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.
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$.
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.
Input
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
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.
Samples
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
1
1 3 2 3 1 4 2
1
1 1 1 2 2
0
13 31 25 12 14 10