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

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