Soccer Bets

Time limit1sMemory limit128 MB

Summary

16 shuffled match results with scores are given; reconstruct the single-elimination bracket and report the tournament winner.

Level: Medium5 of 10
Topics: Graph, Implementation, Simulation, Hash map
Solved: No attempts yet

Problem

The group stage of the FIFA World Cup is over, and the sixteen teams in the round of sixteen are known. My boss has had every remaining game analysed and has bet on the whole rest of the tournament, writing the outcome of each match on a single sheet of paper. My job was to take his bets to the nearest betting office and stake 1,000 dollars. Being nervous with so much cash in my pockets, I tripped (I am a little clumsy) and the bets got shuffled. So now I no longer know whether a given bet belongs to the final, a semi-final, or some other match.

I do not want to disappoint my boss, so I have decided to place just one bet: on the winner of the tournament. All I know is that in each round the teams that win advance to the next round (a team wins if it scores more goals than its opponent), and the losing teams are knocked out. The only exception is the semi-finals, whose two losers still play each other for third place. In total, then, there are 16 matches.

Based on my boss's bets, can you tell me which team will win the World Cup?

Input

The first line contains the number of test cases $c$ $(1 \le c \le 100)$ . Each test case consists of 16 lines that describe the matches in random order. A match is described as t1 t2 g1 g2, where $t_1$ and $t_2$ are the names of the two teams (each abbreviated as exactly three uppercase letters) and $g_1$ and $g_2$ $(0 \le g_1, g_2 \le 10;\ g_1 \ne g_2)$ are the goals scored by $t_1$ and $t_2$ respectively.

Output

For each test case, print a single line with the team that will win the FIFA World Cup (according to my boss's analysis, which is always correct).

Examples3

Example 1

Input

1
ITA URU 2 0
ITA IRE 1 0
ITA ARG 3 4
YUG ARG 2 3
GER CZE 1 0
ENG GER 3 4
ITA ENG 2 1
CAM COL 2 1
ENG CAM 3 2
ENG BEL 1 0
GER ARG 1 0
CZE CRC 4 1
NET GER 1 2
BRZ ARG 0 1
SPA YUG 1 2
ROM IRE 4 5

Expected output

GER

Example 2

Input

1
ENG URU 8 10
CRO GER 9 1
ARG ESP 0 6
POR ESP 4 7
KOR BEL 3 0
ESP BRA 10 7
ARG KOR 10 6
ENG MEX 4 1
ARG URU 4 8
FRA URU 3 8
ESP CRO 5 8
POR JPN 4 2
NED ITA 10 0
USA ARG 0 8
NED CRO 1 9
URU CRO 6 3

Expected output

URU

Example 3

Input

3
USA URU 5 0
JPN ENG 7 0
KOR ARG 5 7
URU MEX 7 4
GER ITA 3 5
NED CRO 4 8
CRO ARG 2 9
ARG USA 1 0
POR USA 0 1
ESP FRA 3 9
JPN USA 2 6
BEL GER 0 10
FRA JPN 0 9
ITA BRA 10 2
ITA JPN 7 4
ITA ARG 1 5
ENG USA 6 7
CRO NED 4 8
BRA POR 4 3
USA NED 3 6
GER URU 1 5
URU BRA 3 2
MEX URU 0 4
MEX ITA 10 8
ARG URU 4 8
ARG KOR 2 1
KOR ESP 8 0
BRA FRA 7 6
POR JPN 10 4
NED BRA 6 10
ARG NED 0 3
ARG BEL 9 2
KOR CRO 5 2
GER BEL 5 1
NED ARG 10 7
ITA NED 1 3
GER ENG 9 1
JPN NED 0 9
BEL ARG 10 2
KOR ARG 4 8
FRA ARG 2 3
GER NED 3 0
ESP BEL 8 10
POR BRA 6 2
ITA MEX 7 4
GER POR 9 4
ESP URU 10 6
BEL USA 4 0

Expected output

ARG
URU
GER