Gahui and the Suin-Bundang Line 1

Downbound means the direction of travel from Seoul toward the terminus.

On the Suin-Bundang Line, K209 (Cheongnyangni) is in Seoul and K272 (Incheon) is in Incheon, so the direction from K209 to K272 is downbound.

[Figure 1] The downbound direction of the Suin-Bundang Line

A station number on the Suin-Bundang Line is written Kddd, where ddd is an integer from 209 to 272 inclusive. This is because K209 is Cheongnyangni and K272 is Incheon.

In the downbound direction, the next station after the station numbered Kddd is KDDD, where DDD is the integer ddd + 1, except for K272 (Incheon), which has no next station.

A downbound train runs by the following algorithm.

1. It departs the starting station at HH:mm and moves to the next station.
2. When the train arrives at a station, it stays there for 20 seconds. After the 20 seconds, it closes its doors and departs.
3. If the station is the terminus, the train stops running. Otherwise it moves to the next station and performs step 2.

For example, suppose a downbound train starts at the station numbered K210 and ends its run at K233.

[Figure 2] A downbound train with K233 as its terminus arriving at K232

Figure 2 shows a downbound train whose starting station is K210 and whose terminus is K233, both at the moment it arrives at K232 and 20 seconds after that arrival.

K232 is not the terminus, so 20 seconds after arriving at K232 the train departs K232 and heads toward K233.

[Figure 3] A downbound train with K233 as its terminus arriving at K233

Figure 3 shows a downbound train whose starting station is K210 and whose terminus is K233, both at the moment it arrives at K233 and 20 seconds after that arrival.

K233 is the terminus, so a train that arrives at K233 ends its run 20 seconds after arriving there. A train that has ended its run is not shown in the figure.

The travel time from one station to the next is 2 minutes, except for the cases in Table 1.

[Table 1] Cases where the travel time between adjacent stations is 3 minutes or more

Gahui wants to travel from Moran Station, numbered K225, to Incheon Station, numbered K272, riding only Suin-Bundang Line trains.

Find the time at which she can arrive at Incheon Station the earliest.

The first line gives the time at which Gahui arrives at Moran Station, in the format HH:mm:ss. It is always a valid time.

The second line gives N, the number of downbound Suin-Bundang Line train schedules.

From the third line to the N+2-th line, each line gives the station number of the starting station where the train begins its run, the station number of the terminus where the train ends its run, and the departure time from the starting station.

The departure time from the starting station is in the format HH:mm. It is always a valid time.

For example, if a schedule is given as K210 K272 11:20, it means a train that departs K210 (Wangsimni) at 11:20 and ends its run at K272 (Incheon).

Print the earliest time of arrival at Incheon Station in the format HH:mm:ss.

If HH, mm, or ss is less than 10, pad it with a leading zero. For example, if the answer is 9 hours 1 minute 0 seconds, print 09:01:00, not 9:1:0.

If Gahui cannot reach Incheon Station, numbered K272, by 23:59:59 today riding only Suin-Bundang Line trains, print -1.

• 1 ≤ N ≤ 400
• The starting station and terminus of a train are each one of K210, K233, K246, K258, K272, and the starting station comes before the terminus in dictionary order.
• Trains also stop at K268 (Hagik).
• From the starting station, the first train departs at or after 04:45 and the last train departs before 23:45. That is, every time in the downbound train schedules is at or after 04:45 and before 23:45.
• Trains neither arrive early nor run late.
• No two downbound trains are ever at the same station at the same time.
• In the HH:mm:ss and HH:mm formats, HH is an integer in the range [0, 23], and mm and ss are integers in the range [0, 59]. If HH, mm, or ss is less than 10, it is padded with a leading zero.

• The starting station is where a train begins its run, and the terminus is where it ends its run. For example, if the starting station is K258 and the terminus is K272, the train departs K258 (Oido) and stops at the following stations in order.
  • K259 (Dalwol), K260 (Wolgot), K261 (Soraepogu), K262 (Incheon Nonhyeon), K263 (Hogupo), K264 (Namdong Induspark), K265 (Woninjae), K266 (Yeonsu), K267 (Songdo), K268 (Hagik), K269 (Inha University), K270 (Sungui), K271 (Sinpo), K272 (Incheon)