The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 3:

- Kotlin 1.4.0

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Movie Fan

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputRecently, 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

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.

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

Output

1 1 3 2 3 1 4 2 1 1 1 1 2 2 0 13 31 25 12 14 10

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/01/2020 07:43:56 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|