Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Ruby
Branch: master

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
lib
spec
.gitignore
Gemfile
LICENSE
README.md
Rakefile
notes.markdown
tourist.gemspec

README.md

[#2] Cheap tourist, fast tourist

This puzzle was contributed by Felipe Doria and published on March 15, 2011

UPDATE #2: Note that in the example below, flight plans are for a single day and may not span across multiple days

Steve and Jennifer are planning a trip across the country. No airline offers direct flights to their destination, so they are having a hard time choosing the appropriate sequence of flights to take. Steve is quite cheap so he wants the least expensive sequence of flights. Jennifer on the other hand hates spending time in planes and airports so she wants the quickest sequence between their origin and destination.

After a heated discussion they decide that each one will take a different sequence of flights and meet at the destination city's hotel.

Note that even if they are quite picky they are not stupid. If there are two flight sequences that take the same time, Jennifer will pick the cheapest of the two, and if there are two flight sequences that cost the same, Steve will pick the fastest one.

All the flights are scheduled for a single day and both Steve and Jennifer trips should happen within this day (they can't take a multi-day flight).

Problem


Given that Steve and Jennifer want to travel from city A to city Z, find the sequence of flights most suitable for each one. Steve wants the cheapest sequence whereas Jennifer wants the fastest.

Input


The first line of the input file contains an integer specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with a single number N giving the number of flights available. Each of the following N lines contains data for one flight in the format "FROM TO DEPARTURE ARRIVAL PRICE", where DEPARTURE is the time that the plane leaves the FROM city, ARRIVAL is the time that the plane reaches the TO city, and PRICE is how much the ticket cost.

Output


For each test case output two lines with the information about the sequence of flights chosen in the format "DEPARTURE ARRIVAL PRICE", where DEPARTURE is the time that the first flight leaves city A, ARRIVAL is the time that the last flight reaches city Z and PRICE is the total cost for the trip.

The first line should show info about Steve's sequence and the second about Jennifer's.

Example


Input

2



3

A B 09:00 10:00 100.00

B Z 11:30 13:30 100.00

A Z 10:00 12:00 300.00



7

A B 08:00 09:00 50.00

A B 12:00 13:00 300.00

A C 14:00 15:30 175.00

B C 10:00 11:00 75.00

B Z 15:00 16:30 250.00

C B 15:45 16:45 50.00

C Z 16:00 19:00 100.00

Output

09:00 13:30 200.00

10:00 12:00 300.00



08:00 19:00 225.00

12:00 16:30 550.00

You can use the sample files from this example to test your program before submitting an answer for the real dataset for this problem.

Something went wrong with that request. Please try again.