Exam Example 1

Best Train Connection

Hugo is going to travel by train from station A to station B. Unfortunately, there is no direct train connection from A to B. Hugo will have to go by train to another station C, and from there take another train to B. This means that the journey will consist of exactly two consecutive train connections. It does not matter which station will be chosen as a transfer station C.

Hugo has a list of all train connections between the stations in the region. He wants to complete the journey in a single day and he wants the duration of the journey to be as short a possible. However, he is limited by the transfer time. He decided he will consider only those pair of connections in which the second connection departs at least 10 minutes after the arrival of the first connection.

The duration of a journey is the difference between the arrival time of the second connection and the departure time of the first connection. The transfer duration of a journey is the difference between the departure time of the second connection and the arrival time of the first connection.

A journey X is considered better than a journey Y if and only if either the duration of X is smaller than the duration of Y or the duration of X and Y is the same and the transfer duration of X is bigger than the transfer duration of Y.

The task

Write a program that will automate the search for the best connection.

Input description

The first input line contains a positive integer N, the number of connections in the list. The second and the third line contain the name of the start and the end station of the journey, respectively. The list of connections occupies next N lines, each line describes one connection. A connection description consists of four items. The first and the fourth items are different station names. The second item is the departure time from the station specified in the first item. The third item is the arrival time to the station specified in the fourth item. Each time item consists of hour and minute specification, both are two digits long and are separated by a colon. All items on a line are separated by spaces. The value of N is between 2 and 1000. The station names do not contain digits or colons.

Output description

The output consists of two lines. The first line contains the duration of the best journey. The the second line contains the duration of the best journey decreased by the transfer duration of that journey. Both durations are presented in the HH:MM format which is the same as the format of times in the input. It is guaranteed that there is always at least one best journey.

Example 1

Input

5
A
B
A 01:00 02:30 C
A 01:00 02:00 C
C 03:00 04:30 B
C 02:30 03:30 B
C 03:00 04:00 B

Output

02:30
02:00

Comment. The connections in the best journey are

A 01:00 02:00 C
C 02:30 03:30 B

Example 2

Input

7
Mossley West
Ashtown
Mossley West 15:29 16:18 Titanic Quarter/Bridge End
Tara Street 08:33 09:54 Ashtown
Mossley West 06:28 08:22 Tara Street
Tara Street 12:40 14:34 Ashtown
Mossley West 09:55 12:27 Tara Street
Titanic Quarter/Bridge End 14:20 17:11 Tara Street
Mossley West 06:38 07:41 Tara Street

Output

03:16
02:24

Comment. The connections in the best journey are

  Mossley West 06:38 07:41 Tara Street
  Tara Street 08:33 09:54 Ashtown

Example 3

Input

25
Rosslare Strand
Oranmore
Kilcock 03:53 04:27 Rosslare Strand
Rosslare Strand 01:18 03:25 Lurgan
Gort 08:48 09:35 Rosslare Strand
Rosslare Strand 16:02 17:47 Kilcock
Lurgan 12:14 13:21 Oranmore
Oranmore 10:54 13:49 Rosslare Strand
Rosslare Strand 08:07 09:28 Gort
Oranmore 18:38 20:37 Kilcock
Gort 07:59 10:28 Rosslare Strand
Kilcock 16:39 19:28 Oranmore
Lurgan 15:59 18:42 Oranmore
Oranmore 12:48 13:54 Rosslare Strand
Kilcock 19:25 20:57 Lurgan
Kilcock 03:09 05:25 Gort
Kilcock 02:44 05:10 Rosslare Strand
Kilcock 03:36 05:22 Gort
Gort 12:52 15:08 Rosslare Strand
Rosslare Strand 04:02 05:14 Lurgan
Kilcock 06:33 09:05 Rosslare Strand
Rosslare Strand 07:55 09:57 Kilcock
Gort 18:30 19:11 Kilcock
Oranmore 01:57 03:51 Rosslare Strand
Gort 08:48 11:46 Kilcock
Gort 07:55 10:12 Oranmore
Kilcock 17:25 19:28 Lurgan

Output

09:19
02:19

Comment. The connections in the best journey are

Rosslare Strand 04:02 05:14 Lurgan
Lurgan 12:14 13:21 Oranmore


Training data

download

courses/be5b33pge/practices/examexample1.txt · Last modified: 2020/05/03 07:05 by berezovs