Монокарп недавно устроился на работу, его рабочий день длится \(m\) минут. Также известны \(n\) минут \(a_1, a_2, \dots, a_n\), в которые он хочет сделать перерыв на кофе (в этой задаче считаем, что Монокарп пьет кофе ровно минуту).
Однако начальнику Монокарпа не нравится, когда тот пьет кофе слишком часто, поэтому Монокарп хочет проставить каждой из заданных минут \(a_i\) номер рабочего дня, в который он устроит перерыв на кофе в эту минуту, так, чтобы каждый день между любой парой перерывов на кофе было как минимум \(d\) минут рабочего времени. При этом Монокарп хочет попить кофе \(n\) раз за минимальное количество именно рабочих дней (исключая выходные). Считайте, что между любыми двумя последовательными рабочими днями проходит более \(d\) минут.
Определите для каждой из \(n\) заданных минут для перерывов на кофе, в какой из дней соответствующий перерыв нужно сделать. При этом количество дней нужно минимизировать.
Выходные данные
В первую строку выведите минимальное количество дней, в которые Монокарп успеет сделать описанные \(n\) перерывов на кофе.
Во вторую строку выведите \(n\) целых чисел, причем \(i\)-е число должно быть равно номеру рабочего дня, в который нужно сделать перерыв на кофе в минуту \(a_i\). Дни нужно нумеровать последовательными натуральными числами, начиная с \(1\). Если ответов несколько, разрешается вывести любой из них.
Примечание
В первом примере Монокарп может сделать два перерыва на кофе в первый день (в минуты \(1\) и \(5\), между ними пройдёт \(3\) минуты), один перерыв на кофе во второй день (в минуту \(2\)) и один перерыв на кофе в третий день (в минуту \(3\)).
Во втором примере Монокарп может сделать все перерывы в нечетные минуты в первый день, а все перерывы в четные минуты во второй.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5 3
3 5 1 2
|
3
3 1 1 2
|
|
2
|
10 10 1
10 5 7 4 6 3 2 1 9 8
|
2
2 1 1 2 2 1 2 1 1 2
|