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
saket diwakar: 2012-01-08 18:36:15

easy one....

Surya: 2011-07-22 04:12:21

Watch out! The teams in different test cases can be different..

Santiago Palacio: 2011-06-11 08:05:51

Ok, got AC, i didn't saw the comment, thanks anyway.

Adrian Kuegel: 2011-06-08 11:38:21

Yes, there are no ties. Now think what condition must hold for the overall winner.

Santiago Palacio: 2011-06-04 15:20:58

Ther are no ties? what if two teams win the same ammount of matches, is it chosen by the number of goals?

Rachmawan Atmaji Perdana: 2011-05-06 09:17:51

It's really really really easy problem XD

hendrik: 2010-07-03 21:03:02

I think you should update the test cases a little:
ENG GER 1 4
GER ARG 4 0
:-)

Kawmia Institutes: 2010-07-01 22:06:43

easy for beginners but it can be classical

Adrian Kuegel: 2010-06-23 10:27:31

I know this problem is very easy, but if someone wants to practice with all problems of the German Collegiate Programming Contest, he will find the problems easier if they are all in classical section. Also, this problem ( https://www.spoj.pl/problems/ACT/ ) is still in classical section and it is as easy as this one.

Last edit: 2010-06-23 10:28:44

Added by:Adrian Kuegel
Date:2010-06-21
Time limit:1s
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)