In some cities there is a chain of restaurants, which has a total of \textbf{N} almost identical rooms. Administration has received applications for \textbf{K} in the pre-day corporate activities. Each application by a specified start and end time (from \textbf{00:00} to \textbf{23:59}). For the one event needed a whole room (which specifically does not matter). After the event should be not less than an hour to prepare for the next event in this room. Required to satisfy the largest possible number of applications. If you can satisfy all, then it should be to use the smallest number of rooms. \InputFile The first line contains the number of \textbf{N} and \textbf{K} (\textbf{1} <= \textbf{N}\textit{, }\textbf{K} <= \textbf{100}). In each of the next \textbf{K} lines contains the start and end of the application in the format \textbf{ЧЧ:ММ-ЧЧ:ММ}. Completion time of each application at least for a moment longer in advance. \OutputFile In the first line, print out two numbers - the number of applications \textbf{P}, which could be met, and the number of halls \textbf{Q}, which had to intervene. In each of these \textbf{P} lines to bring out two numbers - the serial number of the application (as it stood in the input file) and the number of the hall. If the problem has several solutions, then bring up any of them.