Последнее время Поликарп фанатеет от новинок кинематографа и старается их не пропускать!
В ближайшее время выйдут \(n\) новых фильмов: \(i\)-й из них поступит в прокат в день \(a_i\) и закончит прокат в день \(b_i\). Это значит, что если Поликарп хочет посмотреть \(i\)-й фильм в кинотеатре, то должен это сделать в отрезок дней с \(a_i\) по \(b_i\) включительно.
Возможно, у Поликарпа не будет возможности посмотреть фильм в кинотеатре, тогда он может сделать это и после дня \(b_i\), посмотрев его с помощью одного из онлайн-сервисов. Конечно, это нежелательный исход для Поликарпа, ведь весь мир уже успеет обсудить этот фильм в социальных сетях!
В день Поликарп может посмотреть не более \(m\) фильмов. Помогите Поликарпу найти такое расписание просмотра фильмов, что каждый фильм будет просмотрен в кинотеатре. Если такое расписание не существует, то Поликарп хочет смотреть фильмы так, чтобы
- для каждого фильма, который он не успеет посмотреть в кинотеатре найдём количество дней между окончанием его проката и днём, когда Поликарп сможет посмотрит фильм;
- максимальная из величин предыдущего пункта должна быть как можно меньше.
Выходные данные
Выведите \(t\) ответов на заданные наборы входных данных в порядке их записи в тесте: \(i\)-й ответ должен состоять из двух строк. В первую строку ответа выведите целое число \(d\):
- \(d=0\), если существует расписание, что все фильмы просмотрены во время проката;
- \(d>0\), если такого расписания не существует — в этом случае \(d\) равно минимальному значению максимума среди всех «опозданий» просмотров после проката.
Во вторую строку ответа выведите \(n\) положительных целых чисел \(t_1, t_2, \dots, t_n\), где \(t_i\) — номер дня, когда надо посмотреть \(i\)-й фильм, в оптимальном расписании.
Если ответов несколько, то выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|