You have a busy schedule to keep up with. Every time you make a new appointment, you scribble the starting time down on a little note pad. At the start of every day (12:00 a.m.), you sort the appointments for that day from earliest to latest and then go to sleep. Instead of having to be up at midnight every night to sort your appointments, you decide this would be a good job for your computer.
Input contains at most $100$ test cases. Each test case describes the appointments for a single day, starting with a line containing the number of appointments $1 \leq n \leq 100$. Following this are $n$ lines, each containing one appointment time. Each appointment time has the format H:M Z where H is an integer in the range $[1, 12]$ representing the hour, M is a zero-padded two-digit integer in the range $[00, 59]$ representing the minute, and and Z is either ‘a.m.’ or ‘p.m.’ representing times before or after mid-day, respectively. The sequence of test cases ends with a value of zero for $n$.
For each test case, output the sequence of event starting times sorted from earliest to latest in the day, one per line. Format times in the same way as the input. Separate adjacent test case outputs with a blank line.
|Sample Input 1||Sample Output 1|
5 3:00 a.m. 3:00 p.m. 12:00 a.m. 11:59 a.m. 12:00 p.m. 3 3:30 p.m. 9:30 a.m. 3:30 p.m. 0
12:00 a.m. 3:00 a.m. 11:59 a.m. 12:00 p.m. 3:00 p.m. 9:30 a.m. 3:30 p.m. 3:30 p.m.