CF524D.Social Network

Polycarpus got an internship in one well-known social network. His test task is to count the number of unique users who have visited a social network during the day. Polycarpus was provided with information on all user requests for this time period. For each query, we know its time... and nothing else, because Polycarpus has already accidentally removed the user IDs corresponding to the requests from the database. Thus, it is now impossible to determine whether any two requests are made by the same person or by different people.

But wait, something is still known, because that day a record was achieved — M simultaneous users online! In addition, Polycarpus believes that if a user made a request at second s, then he was online for T seconds after that, that is, at seconds s, s + 1, s + 2, ..., s + T - 1. So, the user's time online can be calculated as the union of time intervals of the form [s, s + T - 1] over all times s of requests from him.

Guided by these thoughts, Polycarpus wants to assign a user ID to each request so that:

• the number of different users online did not exceed M at any moment,
• at some second the number of distinct users online reached value M,
• the total number of users (the number of distinct identifiers) was as much as possible.

Help Polycarpus cope with the test.

波利卡普斯在一家知名社交网络公司获得了实习机会。他的测试任务是统计当天访问该社交网络的唯一用户数量。波利卡普斯已获得该时段内所有用户的请求记录。对于每个请求，我们仅知道其发生时刻……其余信息一概未知，因为波利卡普斯已不慎将与这些请求相对应的用户 ID 从数据库中删除了。因此，目前无法判断任意两个请求是否来自同一用户或不同用户。

但等等，仍有一些信息是已知的：当天创下了在线用户数的最高纪录——M 个用户同时在线！此外，波利卡普斯认为：若某用户在第 s 秒发起一次请求，则此后他将持续在线 T 秒，即在第 s, s + 1, s + 2, ..., s + T - 1 秒均处于在线状态。因此，该用户的总在线时间可表示为所有其请求时刻 s 所对应的时间区间 [s, s + T - 1] 的并集。

基于上述思路，波利卡普斯希望为每个请求分配一个用户 ID，使得：

• 在任意时刻，在线的不同用户数量均不超过 M；
• 在某一时刻，在线的不同用户数量恰好达到 M；
• 用户总数（即不同标识符的总数）尽可能多。

请帮助波利卡普斯完成这项测试任务。

The first line contains three integers n, M and T (1 ≤ n, M ≤ 20 000, 1 ≤ T ≤ 86400) — the number of queries, the record number of online users and the time when the user was online after a query was sent. Next n lines contain the times of the queries in the format "hh:mm:ss", where hh are hours, mm are minutes, ss are seconds. The times of the queries follow in the non-decreasing order, some of them can coincide. It is guaranteed that all the times and even all the segments of type [s, s + T - 1] are within one 24-hour range (from 00:00:00 to 23:59:59).

第一行包含三个整数 $n$、$M$ 和 $T$（$1 ≤ n, M ≤ 20\,000$，$1 ≤ T ≤ 86400$）——分别表示查询次数、在线用户数的历史最高纪录，以及用户在发送查询后保持在线的时间长度。接下来的 $n$ 行每行包含一个查询发生的时间，格式为“hh:mm:ss”，其中 hh 表示小时，mm 表示分钟，ss 表示秒。这些查询时间按非递减顺序给出，部分时间可能相同。保证所有时间点，甚至所有形如 $[s,\,s+T-1]$ 的时间段，均落在同一个 24 小时范围内（即从 00:00:00 到 23:59:59）。

In the first line print number R — the largest possible number of distinct users. The following n lines should contain the user IDs for requests in the same order in which the requests are given in the input. User IDs must be integers from 1 to R. The requests of the same user must correspond to the same identifiers, the requests of distinct users must correspond to distinct identifiers. If there are multiple solutions, print any of them. If there is no solution, print "No solution" (without the quotes).

第一行输出整数 $R$ —— 可能的最大不同用户数量。接下来的 $n$ 行应按输入中请求给出的相同顺序，输出各请求对应的用户 ID。用户 ID 必须为 $1$ 到 $R$ 之间的整数。同一用户的请求必须对应相同的标识符，不同用户的请求必须对应不同的标识符。若存在多种解法，输出任意一种即可。若无解，则输出 No solution（不带引号）。

Consider the first sample. The user who sent the first request was online from 17:05:53 to 17:06:02, the user who sent the second request was online from 17:05:58 to 17:06:07, the user who sent the third request, was online from 17:06:01 to 17:06:10. Thus, these IDs cannot belong to three distinct users, because in that case all these users would be online, for example, at 17:06:01. That is impossible, because M = 2. That means that some two of these queries belonged to the same user. One of the correct variants is given in the answer to the sample. For it user 1 was online from 17:05:53 to 17:06:02, user 2 — from 17:05:58 to 17:06:10 (he sent the second and third queries), user 3 — from 22:39:47 to 22:39:56.

In the second sample there is only one query. So, only one user visited the network within the 24-hour period and there couldn't be two users online on the network simultaneously. (The time the user spent online is the union of time intervals for requests, so users who didn't send requests could not be online in the network.)

考虑第一个样例。发送第一个请求的用户在线时间为 17:05:53 至 17:05:53，发送第二个请求的用户在线时间为 17:05:58 至 17:06:07，发送第三个请求的用户在线时间为 17:06:01 至 17:06:10。因此，这些 ID 不可能属于三个不同的用户，因为若如此，则所有这三位用户在例如 17:06:01 这一时刻均处于在线状态，而这与 M = 2 矛盾（即网络最多同时容纳 2 名用户）。这意味着其中两个查询必然属于同一用户。样例答案中给出了一种合法方案：用户 1 的在线时间为 17:05:53 至 17:06:02；用户 2 的在线时间为 17:05:58 至 17:06:10（他发送了第二个和第三个请求）；用户 3 的在线时间为 22:39:47 至 22:39:56。

在第二个样例中仅有一个查询。因此，在 24 小时周期内仅有一名用户访问了该网络，且不可能存在两名用户同时在线。（用户在线时间为其所有请求对应时间区间的并集，因此未发送任何请求的用户不可能处于在线状态。）