Polycarpus 在一家知名社交网络获得了实习机会。他的测试任务是计算白天访问过社交网络的唯一用户数量。 Polycarpus 获得了该时间段内所有用户请求的信息。对于每个查询,我们只知道它的时间……除此之外别无其他,因为 Polycarpus 已经意外地从数据库中删除了与请求相对应的用户 ID。因此,现在无法确定任意两个请求是同一个人还是不同人提出的。
但是等等,有些事情还是已知的,因为那天创下了一项记录——M 同时在线!另外,Polycarpus 认为,如果用户在 s 秒发出请求,那么此后他在线了 T 秒,即在 s, s + 1, s + 2, ..., s + T - 1 秒。因此,用户的在线时间可以通过其所有 s 次请求的时间间隔([s, s + T - 1])的并集来计算。
在这些想法的指导下,Polycarpus 希望为每个请求分配一个用户 ID,以便:
- 任意时刻在线的不同用户数不超过M,
- 在某一秒,在线不同用户数量达到值 M,
- 用户总数(不同标识符的数量)尽可能多。
帮助Polycarpus应对考验。
输入
第一行包含三个整数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)。
输出
在第一行打印数字 R — 不同用户的最大可能数量。以下 n 行应包含请求的用户 ID,其顺序与输入中给出的请求的顺序相同。用户ID必须是1到R之间的整数。同一用户的请求必须对应相同的标识符,不同用户的请求必须对应不同的标识符。如果有多个解决方案,请打印其中任何一个。如果没有解决方案,则打印“无解决方案”(不带引号)。
示例
输入 #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
注意
考虑第一个样本。发送第一个请求的用户在线时间为 17:05:53 至 17:06:02,发送第二个请求的用户在线时间为 17:05:58 至 17:06:07,发送第三个请求的用户在线时间为 17:06:01 至 17:06:10。因此,这些 ID 不能属于三个不同的用户,因为在这种情况下,所有这些用户都将在线(例如,在 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。
在第二个示例中只有一个查询。因此,24小时内只有一名用户访问网络,并且网络上不能同时有两名用户在线。 (用户在线时间是请求时间间隔的并集,因此没有发送请求的用户无法在网络中在线。)