List Analysis

Time Limit: 10 Seconds Memory Limit: 32768 KB

Speed violation detection is not a simple task. After the speed of a vehicle is determined, there are several rules that should be considered before ticketing the car.

1- The speed limit in different routs may be different. For example the speed limit in Modarres highway is 80km/h but in Hemmat highway is 100km/h

2- The speed limit in different hours may differ. For example in Hemmat highway it is 70km/h after 11:00 pm till 5:00 am

3- Also the speed limit for different types of vehicles is different. For example in highways the speed limit for heavy vehicles is 30km/h lower than the other vehicles.

Having a list of passing vehicles in different routs of the city and a set of rules and information about the speed limits and vehicle types, you are asked to write a program that determines the vehicles that should be given a ticket for speeding.

You can assume that there will be enough information to determine correctly.

Input

The input consists of 3 parts.

First part consists of several lines, each line describing a speed limit rule for a route in a specific time (times are inclusive). Each line is in the following format:

<highway name> : <start time>-<end time> : <vehicle type> : <speed limit>

Second part is a list of vehicles’ types as follows

And the third part is the list of passing vehicles from different routs in different times. Each line is as follows

Remember, if two rules overlap, in the overlapped section only newer rule will apply.

Also consider:

<highway name> : (a~z|A~Z|_)*

<time> : DD:DD:DD (00:00:00 ~ 23:59:59)
<vehicle type> : heavy | light
<speed limit> & <speed> : unsigned integer less than 999
<license type> : DD-<letter>-DDD-DD (12-alef-245-22 | 22-dal-143-19)
<letter> : alef | beh | peh | teh | jim | dal | sin | sad | ta | ein | ghaf | kaf | lam | mim | noon | vav | heh | yeh

There might be more or none spaces before and after “:” in order to align the input.

There will be less than 51 highways, 2001 highway rules, 10001 licenses and 100001 queries.

Output

Output the list of the passing vehicles which have violated the speed limit. (their speed is bigger than speed limit)

The output list should be sorted alphabetically increasing, according to their license plate strings. If there are more than one entries of a vehicle, they should be sorted according to their passing time. If same passing times exist, they should be sorted according to their highway names. If same highway names exist, they should be sorted decreasingly according to their speed.

The list should be aligned using extra spaces using the least possible spaces. Licenses have to be left-aligned and speeds have to be right-aligned. There must be at least one space before and at least one space after “:” (not the ones in time)

Sample Input

modares     : 06:00:00-22:00:00 : light : 80
modares     : 22:00:00-06:00:00 : light : 70
modares     : 00:00:00-23:59:59 : heavy : 60
shahid_sadr : 00:00:00-23:59:59 : light : 100
shahid_sadr : 00:00:00-23:59:59 : light : 70
22-alef-234-11 : light
11-dal-239-22  : heavy
12-vav-223-33  : light
99-noon-453-11 : light
11-dal-239-22  : 160 : 09:23:09 : modares
99-noon-453-11 : 75 : 04:23:34 : shahid_sadr
11-dal-239-22   :  75   : 23:27:29 : modares
11-dal-239-22  :  60 : 07:23:09 : modares

Sample Output

11-dal-239-22  : 160 : 09:23:09 : modares
11-dal-239-22  :  75 : 23:27:29 : modares
99-noon-453-11 :  75 : 04:23:34 : shahid_sadr

Submit

Source: 12th Iran Nationwide Internet Contest III