Day 1 Question 3

Bus Schedule

Input file: bus.in

Output file: bus.out

A city contains several bus routes. Each route consists of a number of stops and busses periodically travel among these stops. A traveller wishes to make a journey from one stop to another, arriving no later than a specified time. Your job is to determine the latest time the traveller may arrive at the initial stop so as to be able to arrive at the destination on time.

The input consists of a number of schedules. A schedule consists of

There are no more than 50 schedules and each schedule has no more than 50 stops. Following the last schedule is a line containing -1.

The busses operate as follows. For each schedule, the bus leaves at the beginning time and visits its stops in order. The time interval between the stops is as indicated in the schedule. At the last stop the bus turns around and revisits the stops in reverse order with the same time intervals. This process repeats until the ending time at which time the bus returns home without visiting any more stops (passengers on the bus at the end time are in serious trouble).

Following the schedules (and the line containing -1) are several traveller requests. Each traveller request consists of

The last traveller request is followed by another line containing -1.

For each traveller request, print the latest time that the traveller can be at the beginning stop and still reach the destination in time. It will always be possible to make the trip.

Sample input

6
22
11
1
2 
3  
4  
5  
6
7  
8 
9
10
11
6
6
6
6
6
6
6
6
6
6
0
24
4
6
16
26
36
20
20
20
-1
1
11
15
0
1
11
14
59
11
36
15
0
-1

Output for Sample Input

14:00
12:00
13:00