Last week’s campaign on healthy and environmentally friendly mobility was a big success. Hundreds of commuters to the EPFL campus traded their car for a ride by bus or metro and gave a very positive feedback. They merely complained about earlier wake-up times necessary to reach the campus on time.

 

 

This is where you enter the story. Try to improve the mood of the people by indicating them the latest time they can leave their house such that they can reach the campus no later than 8h15. Any means are ok to maximize their sleeping time, and all would accept to change bus or metro lines several times during their journey if this helps your planning.

The public transport network is made up of S (0<=S<=100)  stations (numbered from 1 to S) and counts C (0<=C<=1'000)  unidirectional connections that link two stations in regular time intervals, starting from a certain time in the morning and up to 8h15. Note that for any two stations, there might exist several direct shuttle services with different starting time and frequency. You are to answer some students’ request on the latest possible time they can leave from home in order not to be late.

 

INPUT

The input consists of several test-cases separated by an empty line. Each test-case starts with the number of stations S, the number of connections C and the number of requests R on a line. Then come C lines, each describing one shuttle service in the format ‘from’ ‘to’ ‘firstRide’ ‘travelTime’ ‘frequency’ (in minutes). The next R lines each hold two integers, the first being the closest station to the student’s home (come what may, but so early no student would like to walk more than necessary) and the second the time (in minutes) it takes the student to reach that station. The campus is located at station S. Input terminates on a test-case with S=C=R=0, which must not be evaluated.

 

OUTPUT

Answer the requests in the same order as they appeare in the input. For each request, print a line in the form “Leave no later than ‘time’”, where ‘time’ is in the format hh:mm. Add an empty line after each test-case. If there is no way the students can make it on time, output “Doomed to be late”. You can safely assume that the commuters are so experienced in hopping on and off busses that they can change busses in no time at all.

 

SAMPLE INPUT

3 2 2

1 3 07:10 50 15

2 3 08:20 5 5

1 3

2 0

 

3 4 3

2 3 05:30 6 5

1 3 06:11 5 15

1 2 07:01 2 5

3 2 08:00 1 8

1 2

2 1

3 10

 

0 0 0                            

 

SAMPLE OUTPUT

Leave no later than 07:22

Doomed to be late

 

Leave no later than 07:59

Leave no later than 08:04

Leave no later than 08:05