Social Network

题意翻译

## 题目描述 Polycarpus 到某知名社交网络公司实习。他的任务是找出在某天访问网站的不同的人的数量。 Polycarpus 只获得了所有的请求的时间，因为记录请求的用户的数据被他误删了。因此，他现在无法确定两个请求是否是同一个人发出的。 但是，他知道，今天达成了一条记录：在某一时刻，有 $M$ 个人同时在线。除此之外，Polycarpus 相信如果一个用户在第 $s$ 秒发出请求，那么他一定会在线 $T$ 秒（相当是在 $s$ , $s+1$ , $s+2$ , ..., $ s+T-1$ 这段时间在线）。 所以，一个用户的在线时间段可以被表示为若干个集合 $[s,s+T-1]$ 的并集。 被这些思考所引导，Polycarpus 希望给每一条请求分配一个 ID 使得： - 任意时刻在线的不同的人数不超过 $M$ 个。 - 在某些时刻在线的不同的人数恰好有 $M$ 个。 - 一天内访问网站的不同的人的数量越多越好。 请你帮 Polycarpus 完成这个任务。 ## 输入格式 第一行三个整数 $n$,$M$,$T$ （$1 \le n,M \le 20000, 1 \le T \le 86400$），分别表示请求的数量, 记录中 $M$ 人同时在线和每个用户在一次请求后在线的时间。 接下来 $n$ 行，表示每一个请求，格式如下 : `hh:mm:ss` 。表示 $hh$ 点，$mm$ 分, $ss$ 秒的时候。保证请求按照时间顺序给出。保证所有的 $[s,s+T-1]$ 都是同一天内（在 `00:00:00` 到 `23:59:59` 之间的。） ## 输出格式 第一行输出 $R$，表示一天内访问网站的不同用户的个数的最大值。 后 $n$ 行，按照输入顺序给出发出请求的 ID。ID 需要在 $1$ 到 $R$ 之间。每一个人有且只能有一个 ID。 如果有多组解，你可以给出任何一个。 如果没有解，输出 `No solution` 。

题目描述

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.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ M $ and $ T $ ( $ 1<=n,M<=20000 $ , $ 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).

输出格式

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).

输入输出样例

输入样例 #1

4 2 10
17:05:53
17:05:58
17:06:01
22:39:47

输出样例 #1

3
1
2
2
3

输入样例 #2

1 2 86400
00:00:00

输出样例 #2

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.)