Here at Mackenzie, we take great pride in our sports teams. Since winter has come to an end, our school's attention has shifted to the basketball team. They'll be competing for the best team in our region as they hope to make provincials.
In MCPT, we like to analyze other schools and assign power levels to each high school basketball team in our region, including ourselves. There is an upcoming single elimination round robin tournament where teams will be competing.
A simple single elimination round robin tournament consists of an even number of teams in which each team competes in a series of rounds to determine the winner. The first round consists of the matches. The second round consists of the winners of those matches facing off against each other. This continues until there is one team left, who is declared the winner. Note that for this problem, the number of teams will always be a power of . The teams will be listed in their round robin order as shown above.
For example, if the teams are listed as:
William Lyon Mackenzie C.I. Earl Haig Secondary School Marc Garneau C.I. Martingrove C.I.
Then the first round will be William Lyon Mackenzie C.I. vs. Earl Haig Secondary School and Marc Garneau C.I. vs. Martingrove C.I.
Each executive gives their own list of team power levels, with each team having a score from to .
The victor of a match is determined by the average of every executives' power ranking for that team. The team with the higher average power ranking will win the match. If two teams have the same power ranking, the team who is listed first wins. For example, if Marc Garneau C.I. and Martingrove C.I. from above have the same average power ranking, Marc Garneau C.I. would win.
Given the teams participating and their power rankings, we want you to write a program that determines which team will win the tournament.
The first line contains two integers , the number of teams, and , the number of MCPT executives betting.
The next lines will contain a unique name of a team competing. Names will contain only alphanumerical characters, spaces, and periods. Names will consist of at most characters.
The next lines will each contain integers, , representing the power ranking of each team in the order they were listed in.
On the first line, print the two teams in the final match, from top to bottom in the bracket with
vs. in between the two names.
On the second line, print the name of the winning team.
Sample Input 1
2 1 William Lyon Mackenzie C.I. Earl Haig Secondary School 35 43
Sample Output 1
William Lyon Mackenzie C.I. vs. Earl Haig Secondary School Earl Haig Secondary School
Sample Input 2
8 6 Marc Garneau C.I. Martingrove C.I. A Y Jackson Secondary School Oakwood C.I. Georges Vanier Secondary School Winston Churchill C.I. York Mills C.I. Forest Hill C.I. 23 32 65 77 45 42 65 87 45 43 76 12 64 32 32 45 53 34 79 12 93 61 41 56 13 64 89 53 31 64 56 42 64 53 52 76 43 31 67 42 12 45 67 34 32 56 76 85
Sample Output 2
A Y Jackson Secondary School vs. Forest Hill C.I. A Y Jackson Secondary School