Поликарп устроился на стажировку в одну широко известную в узких кругах социальную сеть. Его тестовое задание — посчитать количество уникальных пользователей, посетивших социальную сеть в течение суток. Поликарпу была предоставлена информация о всех запросах пользователей за этот период времени. Для каждого запроса известно его время и... больше ничего не известно, потому что соответствующие запросам идентификаторы пользователей Поликарп уже успел нечаянно удалить из базы данных. Таким образом, теперь невозможно определить, были ли какие-то два запроса сделаны одним и тем же пользователем или разными.
Хотя нет, кое-что все-таки известно, потому что в тот день был достигнут рекорд — M пользователей одновременно в сети! Кроме того, у Поликарпа есть веские основания полагать, что если пользователь сделал запрос в секунду s, то он был в сети в течение T секунд после этого, то есть в секунды s, s + 1, s + 2, ..., s + T - 1. Таким образом, время нахождения пользователя в сети определяется как объединение временных промежутков вида [s, s + T - 1], соответствующих его запросам. В частности, любой пользователь мог находиться в сети с перерывами, то есть временные промежутки не обязаны в объединении давать ровно один отрезок. Если в секунду пришло несколько запросов, то они могли принадлежать как разным пользователям, так и одному и тому же.
Руководствуясь этими соображениями, Поликарп хочет приписать каждому запросу идентификатор пользователя так, чтобы:
- количество различных пользователей в сети в любую секунду не превышало M,
- в некоторую секунду количество различных пользователей в сети достигало значения M,
- общее количество пользователей (количество различных идентификаторов) было как можно больше.
Помогите Поликарпу справиться с тестовым заданием.
Выходные данные
В первой строке выведите число R — наибольшее возможное количество различных пользователей. Следующие n строк должны содержать идентификаторы пользователей для запросов в том же порядке, в каком запросы заданы во входных данных. Идентификаторы пользователей должны быть целыми числами от 1 до R. Запросам одного и того же пользователя должны соответствовать одинаковые идентификаторы, запросам разных пользователей — разные. Если решений несколько, выведите любое. В случае если решения не существует, выведите «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.
Во втором примере только один запрос, следовательно, за сутки сеть посетил только один пользователь и не могло быть двух пользователей в сети одновременно. (Время нахождения пользователя в сети равно объединению временных промежутков для запросов, поэтому пользователи, не отправлявшие запросов, не могли быть в сети.)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2 10
17:05:53
17:05:58
17:06:01
22:39:47
|
3
1
2
2
3
|
|
2
|
1 2 86400
00:00:00
|
No solution
|