Employees at ItsHorribleToWorkHere, Inc. record their long hours by punching a time clock. They punch it when they begin working, and punch it again when they stop.

However, the time clock had a bug where it only recorded the hour and minute of each punch, and the order of punches.

Mr. ItsHorribleToWorkForMe, the CEO and founder of the company, would prefer to pay his employees as little as possible.

Given the records of the time clock, calculate the fewest possible number of hours employees worked. (ItsHorribleToWorkHere is in Arizona, so don't worry about daylight savings.)

For example, if the record looks like this,

10:30 0001
12:00 0001

employee 0001 worked for 1 hour and 30 minutes, or 1.5 hours.

However, in this record,

09:45 1234
10:30 0001
01:13 1234
12:00 0001

0001 must have worked for 13 hours and 30 minutes, or 13.5 hours, since 01:13 is in-between his clock-in at 10:30 and clock-out at 12:00. (Not even Mr. ItsHorribleToWorkMe can argue with that.)

Employee 1234 worked for 3 hours and 28 minutes, or 3.467 hours.

Input

The first line is the number of punches, 0 < N <= 4,000.

The next N lines are the punches, given in order of when they occurred. Each punch consists of a 12-hour time (from 00:01 to 12:00) and the employee ID (a four digit 0-padded number).

The time punch records in complete, in that there were no employees working before the record, and no employees working after the record.

Output

Print each employee id and the decimal number of hours that employee worked. The hours should be accurate within 0.001.

Be sure to minimize the total number of hours worked where possible, or Mr. ItsHorribleToWorkForMe will fire you.

Order your output by employee ID.

Example

Input:
2
10:30 0001
12:00 0001

Output:
0001 1.5

Input:
4
09:45 1234
10:30 0001
01:13 1234
12:00 0001

Output:
0001 13.5
1234 3.467