D. Социальная сеть
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп устроился на стажировку в одну широко известную в узких кругах социальную сеть. Его тестовое задание — посчитать количество уникальных пользователей, посетивших социальную сеть в течение суток. Поликарпу была предоставлена информация о всех запросах пользователей за этот период времени. Для каждого запроса известно его время и... больше ничего не известно, потому что соответствующие запросам идентификаторы пользователей Поликарп уже успел нечаянно удалить из базы данных. Таким образом, теперь невозможно определить, были ли какие-то два запроса сделаны одним и тем же пользователем или разными.

Хотя нет, кое-что все-таки известно, потому что в тот день был достигнут рекорд — M пользователей одновременно в сети! Кроме того, у Поликарпа есть веские основания полагать, что если пользователь сделал запрос в секунду s, то он был в сети в течение T секунд после этого, то есть в секунды s, s + 1, s + 2, ..., s + T - 1. Таким образом, время нахождения пользователя в сети определяется как объединение временных промежутков вида [s, s + T - 1], соответствующих его запросам. В частности, любой пользователь мог находиться в сети с перерывами, то есть временные промежутки не обязаны в объединении давать ровно один отрезок. Если в секунду пришло несколько запросов, то они могли принадлежать как разным пользователям, так и одному и тому же.

Руководствуясь этими соображениями, Поликарп хочет приписать каждому запросу идентификатор пользователя так, чтобы:

  • количество различных пользователей в сети в любую секунду не превышало M,
  • в некоторую секунду количество различных пользователей в сети достигало значения M,
  • общее количество пользователей (количество различных идентификаторов) было как можно больше.

Помогите Поликарпу справиться с тестовым заданием.

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

В первой строке заданы три целых числа n, M и T (1 ≤ n, M ≤ 20 000, 1 ≤ T ≤ 86 400) — количество запросов, рекордное число пользователей онлайн и время нахождения пользователя в сети после отправки запроса. Следующие n строк содержат времена запросов в формате «hh:mm:ss», где hh — часы, mm — минуты, ss — секунды. Времена запросов идут в порядке неубывания, некоторые из них могут совпадать. Гарантируется, что все времена и даже все промежутки вида [s, s + T - 1] находятся в пределах одних суток (с 00:00:00 до 23:59:59).

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

В первой строке выведите число R — наибольшее возможное количество различных пользователей. Следующие n строк должны содержать идентификаторы пользователей для запросов в том же порядке, в каком запросы заданы во входных данных. Идентификаторы пользователей должны быть целыми числами от 1 до R. Запросам одного и того же пользователя должны соответствовать одинаковые идентификаторы, запросам разных пользователей — разные. Если решений несколько, выведите любое. В случае если решения не существует, выведите «No solution» (без кавычек).

Примеры
Входные данные
4 2 10
17:05:53
17:05:58
17:06:01
22:39:47
Выходные данные
3
1
2
2
3
Входные данные
1 2 86400
00:00:00
Выходные данные
No solution
Примечание

Рассмотрим первый пример. Пользователь, отправивший первый запрос, был в сети с 17:05:53 до 17:06:02, пользователь, отправивший второй запрос — с 17:05:58 до 17:06:07, пользователь, отправивший третий запрос — с 17:06:01 до 17:06:10. Таким образом, эти запросы не могут принадлежать трем разным пользователям, потому что тогда бы все эти пользователи были бы в сети, например, в 17:06:01, что невозможно, поскольку M = 2. Значит, какие-то два из этих запросов принадлежали одному пользователю. Один из корректных вариантов представлен в ответе к примеру. Для него пользователь 1 был в сети с 17:05:53 до 17:06:02, пользователь 2 — с 17:05:58 до 17:06:10 (он отправил второй и третий запросы), пользователь 3 — с 22:39:47 до 22:39:56.

Во втором примере только один запрос, следовательно, за сутки сеть посетил только один пользователь и не могло быть двух пользователей в сети одновременно. (Время нахождения пользователя в сети равно объединению временных промежутков для запросов, поэтому пользователи, не отправлявшие запросов, не могли быть в сети.)