# Bus Schedule

### 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

• 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 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 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. It will always be possible to make the trip.

```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
```

```14:00
12:00
13:00
```