| G - EuroBasket Champions |
We are the champions of the EuroBasket 2015! The team of Gasol, Navarro, Reyes, Rudy, Mirotic, Llull, etc. is probably one of the best basketball teams in Europe of all history: winners of the EuroBasket in 2015, 2011, 2009, silver medal in 2008 and 2012 Olympic Games, winners of the Basketball World Cup in 2006... But, what is your ideal quintet?
All players of the Spanish team have been scored from 0 to 100 with respect to a series of features, such as rebounds, assists, average score, free shots, blocks, etc. In this problem, we want to find the best and most balanced team of five players in all features.
We have a set of 10 basketball players (numbered from 4 to 13), and a set of 12 different features. Each player is scored in each feature, with an integer value in the range 0-100.
The objective of this problem is to select the best and most balanced team of 5 players. In particular, we define the score of a team as the geometric mean of the maximum for each feature. In other words, for each feature we consider the maximum of the 5 selected players, and then we take the geometric mean of the 12 maximums.
The ideal team is the set of 5 players with the highest team score. If more than one optimal solution exists, you have to select the one that uses the players with lowest numbers.
The input contains several test cases. The first line contains a number indicating the total number of test cases.
Each test case consists of 10 lines, one line for each player, from player 4 to player 13. Each line contains 12 integer numbers from 0 to 100, separated by blank spaces, indicating the scores of the corresponding player in each feature. Test cases are separated by empty lines.
For each input case, you have to output the ideal team of 5 players. You have to print the numbers of the players in ascending order, and separated by blank spaces. Remember that the players are numbered from 4 to 13; and if there are many optimal solutions, you have to output the one that uses the lower player numbers first.
2
39 62 35 98 54 81 8 27 98 87 94 76
12 66 69 36 62 3 83 49 24 86 100 100
34 31 38 61 58 45 21 65 62 2 82 9
75 78 35 79 15 44 97 10 51 73 12 16
51 99 96 6 56 76 76 51 15 30 69 49
31 50 26 54 11 59 32 13 41 86 52 33
70 20 61 63 84 77 89 30 20 23 86 53
72 74 30 96 74 93 82 41 61 62 36 73
26 56 48 36 68 93 15 22 56 75 1 92
27 30 97 12 13 2 90 87 22 47 36 2
71 59 23 94 40 4 88 93 50 34 94 56
32 76 84 33 71 71 11 57 26 89 15 46
76 71 56 33 15 8 63 10 24 80 85 64
31 39 1 55 26 77 80 56 12 94 46 74
64 24 5 46 48 81 24 42 80 15 14 42
81 40 80 47 77 69 29 17 83 94 79 1
93 22 79 77 58 100 56 67 24 9 5 43
17 52 65 11 47 12 47 79 3 27 99 9
42 39 2 3 89 15 37 65 14 20 7 37
43 13 8 32 96 32 75 30 8 14 71 4
4 5 8 11 13
4 5 7 9 10