SBETS - Soccer Bets

no tags 

The teams have finished the group stage of the FIFA World Cup and the teams that are in the round of the last sixteen are known. My boss has all of the games analyzed and bets on the whole rest of the tournament by writing the outcome of each match on a single sheet of paper. It was my job to bring his bets to the next betting office and set 1000 dollar. Being nervous with so much cash in my pockets I fell over (I am a bit clumsy) and the bets got shuffled. So I don't know if a bet corresponds to the final match or the semi-final or something else.

I do not want to disappoint my boss, so I decided to place only one bet on the winner of the tournament. Everything I know is that in each round the teams that win (a team wins if it shoots more goals than the opposing team) are in the next round, the other teams are eliminated from the tournament. This is not true for the semi-finals where the losers also play for the third place. So we have in total 16 matches.

Can you please tell me which team will win the World Cup based on the bets of my boss?

Input

The first line of the input is the number of test cases c (1 ≤ c ≤ 100). Each test case consists of 16 lines describing the matches in random order. A match description looks as follows: t1 t2 g1 g2. t1 and t2 are the names of teams (abbreviated as exactly three uppercase letters), g1 and g2 (0 ≤ g1, g2 ≤ 10; g1 ≠ g2) are the goals of the two teams.

Output

For each test case, print one line containing the team that will win the FIFA World Cup (based on the analysis of my boss which is always correct!).

Example

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

Output:
GER

hide comments
vivek_rathi: 2018-03-12 17:54:26

AC in 2nd Go!!! ;)

madhavgaba: 2016-12-28 07:36:47

easy made easiest....through maps;P

wewark: 2016-03-10 14:03:57

@Surya Thanks man ':D

krish: 2015-04-16 20:28:58

Easy as hell:).

vimal: 2015-02-04 16:45:53

writing test cases would have been much more difficult than solving :V

Ruchir Sharma: 2014-12-11 08:41:27

Easy one, \n costed me WA.. :/

Rana Saha: 2013-07-30 23:19:05

Easy as pie! :)

Last edit: 2013-07-30 23:27:43
Centurion: 2013-06-08 14:47:23

1000th accepted user :-)

Mayank Thakur: 2013-06-05 08:32:21

my 100th :)


Added by:Adrian Kuegel
Date:2010-06-21
Time limit:0.272s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:German Collegiate Programming Contest 2010 (Author: Tobias Werth)