Part 8 of 15 in Sorting  

Flight Preference by animeshn

Problem statement

Mr. X has to buy a flight ticket for his next trip. He prefers to fly cheap. However, if two flights have same price, he prefers one with shorter flight duration. If two flights have same price and flight duration, he prefers to fly during early hours in a day. Mr. X needs your help. Given description of his flight options in format '{flight number} {departure time} {flight duration} {price}', he wants you to give him three options out of all in decreasing order of his preference.

Input

First line of input will contain a positive integer T = number of test cases. Each test case will contain multiple lines. First line will contain a positive integer N = number of flight options. Next N lines will contain description of flights in format '{flight number} {departure time} {flight duration} {price}' . Departure time will be in format 'HH:mm' where HH is hour in 24 hour clock and mm is minutes. Flight duration will be in minutes.

Output

For each test case, print on a single line flight number of top three options for Mr. X in decreasing order of his preference. The flight numbers should be separated by single space. There should be no space after last flight number on each line.

Sample Input
1
6
EK404 07:35 135 3000
IT404 08:30 165 3500
SG531 05:36 195 2700
AI440 18:20 155 3500
GA321 11:35 205 3000
EK345 15:35 215 2700
Sample Output
SG531 EK345 EK404


To try out your code



Sign in

Sign up