F. Фанат кино
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последнее время Поликарп фанатеет от новинок кинематографа и старается их не пропускать!

В ближайшее время выйдут $$$n$$$ новых фильмов: $$$i$$$-й из них поступит в прокат в день $$$a_i$$$ и закончит прокат в день $$$b_i$$$. Это значит, что если Поликарп хочет посмотреть $$$i$$$-й фильм в кинотеатре, то должен это сделать в отрезок дней с $$$a_i$$$ по $$$b_i$$$ включительно.

Возможно, у Поликарпа не будет возможности посмотреть фильм в кинотеатре, тогда он может сделать это и после дня $$$b_i$$$, посмотрев его с помощью одного из онлайн-сервисов. Конечно, это нежелательный исход для Поликарпа, ведь весь мир уже успеет обсудить этот фильм в социальных сетях!

В день Поликарп может посмотреть не более $$$m$$$ фильмов. Помогите Поликарпу найти такое расписание просмотра фильмов, что каждый фильм будет просмотрен в кинотеатре. Если такое расписание не существует, то Поликарп хочет смотреть фильмы так, чтобы

  • для каждого фильма, который он не успеет посмотреть в кинотеатре найдём количество дней между окончанием его проката и днём, когда Поликарп сможет посмотрит фильм;
  • максимальная из величин предыдущего пункта должна быть как можно меньше.
Входные данные

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте. Далее следуют описания $$$t$$$ наборов входных данных.

Первая строка каждого из наборов содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — количество фильмов и максимальное количество фильмов, сколько Поликарп может просмотреть в день.

Далее в $$$n$$$ строках описаны сами фильмы, по одному в строке, парой целых чисел $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$) — первый и последний день проката для $$$i$$$-го фильма.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Выведите $$$t$$$ ответов на заданные наборы входных данных в порядке их записи в тесте: $$$i$$$-й ответ должен состоять из двух строк. В первую строку ответа выведите целое число $$$d$$$:

  • $$$d=0$$$, если существует расписание, что все фильмы просмотрены во время проката;
  • $$$d>0$$$, если такого расписания не существует — в этом случае $$$d$$$ равно минимальному значению максимума среди всех «опозданий» просмотров после проката.

Во вторую строку ответа выведите $$$n$$$ положительных целых чисел $$$t_1, t_2, \dots, t_n$$$, где $$$t_i$$$ — номер дня, когда надо посмотреть $$$i$$$-й фильм, в оптимальном расписании.

Если ответов несколько, то выведите любой из них.

Пример
Входные данные
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