Canadian Computing Competition: 1998 Stage 2, Day 1, Problem 3

A city contains several bus routes. Each route consists of a number of stops and buses 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

• A beginning time (an exact hour between ~0~ and ~24~).
• An ending time (an exact hour between ~0~ and ~24~).
• A number ~n~ indicating the number of stops on the route.
• A list of ~n~ stop numbers, one per line (each stop has a unique number between ~1~ and ~1000~).
• A list of ~n-1~ time intervals in minutes, one per line.

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 buses 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 at most ~50~ traveller requests. Each traveller request consists of

• the stop at which the journey begins
• the stop at which the journey ends
• the latest time at which the journey can end (hours and minutes on two separate lines).

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. If it is impossible to make a trip, output -1.

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

Sample Output

14:00
12:00
13:00