Everyone knows that 2010 FIFA World Cup is being held in South Africa now. By the decision of BFA (Berland's Football Association) next World Cup will be held in Berland. BFA took the decision to change some World Cup regulations:

  * the final tournament features n teams (n is always even) 
  * the first n / 2 teams (according to the standings) come through to the knockout stage 
  * the standings are made on the following principle: for a victory a team gets 3 points, for a draw — 1 point, for a defeat — 0 points. In the first place, teams are ordered in the standings in decreasing order of their points; in the second place — in decreasing order of the difference between scored and missed goals; in the third place — in the decreasing order of scored goals 
  * it's written in Berland's Constitution that the previous regulation helps to order the teams without ambiguity. 



You are asked to write a program that, by the given list of the competing teams and the results of all the matches, will find the list of teams that managed to get through to the knockout stage.

Input

The first input line contains the only integer n (1 ≤ n ≤ 50) — amount of the teams, taking part in the final tournament of World Cup. The following n lines contain the names of these teams, a name is a string of lower-case and upper-case Latin letters, its length doesn't exceed 30 characters. The following n·(n - 1) / 2 lines describe the held matches in the format name1-name2 num1:num2, where name1, name2 — names of the teams; num1, num2 (0 ≤ num1, num2 ≤ 100) — amount of the goals, scored by the corresponding teams. Accuracy of the descriptions is guaranteed: there are no two team names coinciding accurate to the letters' case; there is no match, where a team plays with itself; each match is met in the descriptions only once.

Output

Output n / 2 lines — names of the teams, which managed to get through to the knockout stage in lexicographical order. Output each name in a separate line. No odd characters (including spaces) are allowed. It's guaranteed that the described regulations help to order the teams without ambiguity.

Examples

Input

4
A
B
C
D
A-B 1:1
A-C 2:2
A-D 1:0
B-C 1:0
B-D 0:3
C-D 0:3


Output

A
D


Input

2
a
A
a-A 2:1


Output

a

Source: codeforces | Difficulty: MEDIUM
Tags: Implementation


Solutions:
import sys
import logging
logging.root.setLevel(level=logging.INFO)
team_size = int(sys.stdin.readline())
teams = {}
for _ in range(team_size):
	name = sys.stdin.readline().strip()
	teams[name] = {'point': 0, 'delta': 0, 'score': 0}
contest_size = team_size * (team_size - 1) // 2
logging.info(teams)
for _ in range(contest_size):
	(team, score) = sys.stdin.readline().strip().split()
	(team1, team2) = team.split('-')
	(score1, score2) = map(int, score.split(':'))
	logging.info(team1)
	logging.info(score1)
	logging.info(team2)
	logging.info(score2)
	teams[team1]['score'] += score1
	teams[team2]['score'] += score2
	teams[team1]['delta'] += score1 - score2
	teams[team2]['delta'] += score2 - score1
	teams[team1]['point'] += bool(score1 >= score2) + 2 * bool(score1 > score2)
	teams[team2]['point'] += bool(score2 >= score1) + 2 * bool(score2 > score1)
logging.info(teams)
rank = sorted(teams.keys(), key=lambda x: (teams[x]['point'], teams[x]['delta'], teams[x]['score']), reverse=True)
logging.info(rank)
knockout = rank[:team_size // 2]
knockout.sort()
print('\n'.join(knockout))


import functools
teams = {}
n = int(input())
for _ in range(n):
	team_name = input()
	teams[team_name] = [0, 0, 0]
for _ in range(n * (n - 1) // 2):
	(match, score) = input().split()
	(team_one, team_two) = match.split('-')
	(score_one, score_two) = map(int, score.split(':'))
	if score_one == score_two:
		teams[team_one][0] += 1
		teams[team_two][0] += 1
	elif score_one < score_two:
		teams[team_two][0] += 3
	else:
		teams[team_one][0] += 3
	teams[team_one][1] += score_one
	teams[team_one][2] += score_two
	teams[team_two][1] += score_two
	teams[team_two][2] += score_one

def my_cmp(a, b):
	a = a[1]
	b = b[1]
	if a[0] != b[0]:
		return a[0] - b[0]
	if a[1] - a[2] != b[1] - b[2]:
		return a[1] - a[2] - (b[1] - b[2])
	return a[1] - b[1]
passed = sorted(teams.items(), key=functools.cmp_to_key(my_cmp))[n // 2:]
passed = [x[0] for x in passed]
passed.sort()
for team in passed:
	print(team)


n = int(input())
score = {}
for i in range(n):
	score[input()] = [0, 0, 0]
for i in range(int(n * (n - 1) / 2)):
	s = input().split()
	p1 = s[0].split('-')[0]
	p2 = s[0].split('-')[1]
	s1 = int(s[1].split(':')[0])
	s2 = int(s[1].split(':')[1])
	score[p1][1] += s1 - s2
	score[p1][2] += s1
	score[p2][1] += s2 - s1
	score[p2][2] += s2
	if s1 > s2:
		score[p1][0] += 3
	elif s1 == s2:
		score[p1][0] += 1
		score[p2][0] += 1
	else:
		score[p2][0] += 3
score = sorted(score.items(), key=lambda x: x[1][0], reverse=True)
for i in range(n):
	for j in range(n - i - 1):
		if score[j][1][0] == score[j + 1][1][0]:
			if score[j][1][1] < score[j + 1][1][1]:
				(score[j], score[j + 1]) = (score[j + 1], score[j])
for i in range(n):
	for j in range(n - i - 1):
		if score[j][1][1] == score[j + 1][1][1]:
			if score[j][1][2] < score[j + 1][1][2]:
				(score[j], score[j + 1]) = (score[j + 1], score[j])
for i in sorted(score[:int(n / 2)], key=lambda x: x[0]):
	print(i[0])


class Info:

	def __init__(self, newTeamName, newPoints, newGoalDiff, newScoredGoals):
		self.teamName = newTeamName
		self.points = newPoints
		self.goalDiff = newGoalDiff
		self.scoredGoals = newScoredGoals

	def __str__(self):
		template = '\n*****************\n'
		template += f'teamName: {self.teamName} \n'
		template += f'points: {self.points} \n'
		template += f'goalDiff: {self.goalDiff} \n'
		template += f'scoredGoals: {self.scoredGoals} \n'
		template += '*****************\n'
		return template

def output(cont: list):
	for it in cont:
		print(it)

def findIndexByName(cont: list, searchName: str) -> int:
	for i in range(len(cont)):
		if cont[i].teamName == searchName:
			return i
	return -1
(n, cont) = (int(input()), [])
for i in range(n):
	cont.append(Info(input(), 0, 0, 0))
for i in range(n * (n - 1) // 2):
	line = input()
	dashIndex = line.index('-')
	spaceIndex = line.index(' ')
	team1Name = line[:dashIndex]
	team2Name = line[dashIndex + 1:spaceIndex]
	colonIndex = line.index(':')
	goal1 = int(line[spaceIndex + 1:colonIndex])
	goal2 = int(line[colonIndex + 1:])
	team1Index = findIndexByName(cont, team1Name)
	team2Index = findIndexByName(cont, team2Name)
	if goal1 > goal2:
		cont[team1Index].points += 3
	elif goal1 < goal2:
		cont[team2Index].points += 3
	else:
		cont[team1Index].points += 1
		cont[team2Index].points += 1
	cont[team1Index].goalDiff += goal1 - goal2
	cont[team2Index].goalDiff += goal2 - goal1
	cont[team1Index].scoredGoals += goal1
	cont[team2Index].scoredGoals += goal2
cont.sort(key=lambda item: (item.points, item.goalDiff, item.scoredGoals), reverse=True)
del cont[n // 2:]
cont.sort(key=lambda item: item.teamName)
for item in cont:
	print(item.teamName)


score = {}
n = int(input())
for i in range(n):
	team = input()
	score[team] = [0, 0, 0]
for _ in range(n * (n - 1) // 2):
	data = input().split()
	teams = data[0].split('-')
	first_team = teams[0]
	sec_team = teams[1]
	scores = data[1].split(':')
	first_tscore = int(scores[0])
	sec_tscore = int(scores[1])
	if first_tscore < sec_tscore:
		score[sec_team][0] += 3
		score[sec_team][1] += sec_tscore - first_tscore
		score[sec_team][2] += sec_tscore
		score[first_team][1] += first_tscore - sec_tscore
		score[first_team][2] += first_tscore
	if first_tscore > sec_tscore:
		score[first_team][0] += 3
		score[first_team][1] += first_tscore - sec_tscore
		score[first_team][2] += first_tscore
		score[sec_team][1] += sec_tscore - first_tscore
		score[sec_team][2] += sec_tscore
	elif first_tscore == sec_tscore:
		score[first_team][0] += 1
		score[first_team][1] += first_tscore - sec_tscore
		score[first_team][2] += first_tscore
		score[sec_team][0] += 1
		score[sec_team][1] += sec_tscore - first_tscore
		score[sec_team][2] += sec_tscore
res = []
for (team, score) in score.items():
	res.append([score[0], score[1], score[2], team])
res = sorted(res)
res.reverse()
nw = []
for i in range(n // 2):
	nw.append(res[i][3])
nw = sorted(nw)
print(*nw, sep='\n')


class Info:

	def __init__(self, newTeamName, newPoints, newGoalDiff, newScoredGoals):
		self.teamName = newTeamName
		self.points = newPoints
		self.goalDiff = newGoalDiff
		self.scoredGoals = newScoredGoals

	def __str__(self):
		pattern = '\n*************************\n'
		pattern += f'teamName: {self.teamName} \n'
		pattern += f'points: {self.points} \n'
		pattern += f'goalDiff: {self.goalDiff} \n'
		pattern += f'scoredGoals: {self.scoredGoals} \n'
		pattern += '*************************\n'
		return pattern

	def __eq__(self, other):
		if isinstance(other, Info):
			return self.teamName == other.teamName and self.points == other.points and (self.goalDiff == other.goalDiff) and (self.scoredGoals == other.scoredGoals)
		return False

def findIndexByName(cont: list, searchName: str) -> int:
	for i in range(len(cont)):
		if cont[i].teamName == searchName:
			return i
	return -1

def output(cont):
	for item in cont:
		print(item)
(n, cont) = (int(input()), list())
for i in range(n):
	cont.append(Info(input(), 0, 0, 0))
for i in range(n * (n - 1) // 2):
	line = input()
	slashInd = line.index('-')
	spaceInd = line.index(' ')
	colonInd = line.index(':')
	team1Name = line[0:slashInd]
	team2Name = line[slashInd + 1:spaceInd]
	goal1 = int(line[spaceInd + 1:colonInd])
	goal2 = int(line[colonInd + 1:])
	team1Index = findIndexByName(cont, team1Name)
	team2Index = findIndexByName(cont, team2Name)
	if goal1 > goal2:
		cont[team1Index].points += 3
	elif goal1 < goal2:
		cont[team2Index].points += 3
	else:
		cont[team1Index].points += 1
		cont[team2Index].points += 1
	cont[team1Index].goalDiff += goal1 - goal2
	cont[team2Index].goalDiff += goal2 - goal1
	cont[team1Index].scoredGoals += goal1
	cont[team2Index].scoredGoals += goal2
cont.sort(key=lambda item: (item.points, item.goalDiff, item.scoredGoals), reverse=True)
del cont[n // 2:]
cont.sort(key=lambda item: item.teamName)
for item in cont:
	print(item.teamName)


n = int(input())
d = dict()
for i in range(n):
	d[input()] = [0, 0, 0]
for i in range(n * (n - 1) // 2):
	(t, s) = input().split()
	(t1, t2) = t.split('-')
	(s1, s2) = [int(x) for x in s.split(':')]
	a = d[t1]
	b = d[t2]
	a[2] += s1
	b[2] += s2
	a[1] += s1 - s2
	b[1] += s2 - s1
	if s1 == s2:
		a[0] += 1
		b[0] += 1
	elif s1 < s2:
		b[0] += 3
	else:
		a[0] += 3
list = (b for (a, b) in sorted(((b, a) for (a, b) in d.items()))[n // 2:])
print('\n'.join(sorted(list)))


clasificados = []
equipos = []
puntos = []
dg = []
gf = []
n = int(input())
for i in range(n):
	equipos.append(input())
	puntos.append(0)
	dg.append(0)
	gf.append(0)
n_partidos = n * (n - 1) // 2
for i in range(n_partidos):
	partido = input()
	(equipos_partido, resultado) = partido.split()
	(e1, e2) = equipos_partido.split('-')
	goles = resultado.split(':')
	(g1, g2) = (int(goles[0]), int(goles[1]))
	if g1 > g2:
		p1 = 3
		p2 = 0
	elif g1 == g2:
		p1 = 1
		p2 = 1
	else:
		p1 = 0
		p2 = 3
	a = equipos.index(e1)
	b = equipos.index(e2)
	puntos[a] = puntos[a] + p1
	dg[a] = dg[a] + g1 - g2
	gf[a] = gf[a] + g1
	puntos[b] = puntos[b] + p2
	dg[b] = dg[b] + g2 - g1
	gf[b] = gf[b] + g2
	x = 0
for i in range(n // 2):
	mayor = 0
	for j in range(n):
		if mayor != j:
			if puntos[mayor] < puntos[j]:
				mayor = j
			elif puntos[mayor] == puntos[j]:
				if dg[mayor] < dg[j]:
					mayor = j
				elif dg[mayor] == dg[j]:
					if gf[mayor] < gf[j]:
						mayor = j
	clasificados.append(equipos[mayor])
	puntos[mayor] = -1
clasificados.sort()
for i in range(n // 2):
	print(clasificados[i])


(dictionary, commands) = ({}, int(input()))
for i in range(commands):
	dictionary[input()] = [0, 0, 0]
for i in range(commands * (commands - 1) // 2):
	t = input().split()
	(participant1, participant2) = t[0].split('-')
	(score1, score2) = t[1].split(':')
	(score1, score2) = (int(score1), int(score2))
	if score1 > score2:
		dictionary[participant1][0] += 3
	elif score1 < score2:
		dictionary[participant2][0] += 3
	else:
		dictionary[participant1][0] += 1
		dictionary[participant2][0] += 1
	dictionary[participant1][1] += score2
	dictionary[participant2][1] += score1
	dictionary[participant1][2] += score1
	dictionary[participant2][2] += score2
for c in dictionary:
	dictionary[c][1] = dictionary[c][2] - dictionary[c][1]
r = sorted(dictionary.items(), reverse=True, key=lambda x: x[1])
print('\n'.join(sorted((r[i][0] for i in range(commands // 2)))))


from collections import defaultdict

def score(x, y):
	if x > y:
		return 3
	if x == y:
		return 1
	return 0
n = int(input())
players = [input() for _ in range(n)]
mp = defaultdict(lambda : [0, 0, 0])
for _ in range(n * (n - 1) // 2):
	(part1, part2) = input().split()
	(p1, p2) = part1.split('-')
	(g1, g2) = [int(x) for x in part2.split(':')]
	mp[p1][0] += score(g1, g2)
	mp[p1][1] += g1 - g2
	mp[p1][2] += g1
	mp[p2][0] += score(g2, g1)
	mp[p2][1] += g2 - g1
	mp[p2][2] += g2
print('\n'.join(sorted(map(lambda v: v[-1], list(reversed(sorted((v + [k] for (k, v) in mp.items()))))[:n // 2]))))


score = {}
n = int(input())
for i in range(n):
	team = input()
	score[team] = [0, 0, 0]
for _ in range(n * (n - 1) // 2):
	s = input().split()
	teams = s[0].split('-')
	a = teams[0]
	b = teams[1]
	scores = s[1].split(':')
	a_score = int(scores[0])
	b_score = int(scores[1])
	if a_score < b_score:
		score[b][0] += 3
		score[b][1] = score[b][1] + b_score - a_score
		score[b][2] += b_score
		score[a][1] = score[a][1] + a_score - b_score
		score[a][2] += a_score
	if a_score > b_score:
		score[a][0] += 3
		score[a][1] += a_score - b_score
		score[a][2] += a_score
		score[b][1] += b_score - a_score
		score[b][2] += b_score
	elif a_score == b_score:
		score[a][0] += 1
		score[a][1] += a_score - b_score
		score[a][2] += a_score
		score[b][0] += 1
		score[b][1] += b_score - a_score
		score[b][2] += b_score
res = []
for (team, score) in score.items():
	res.append([score[0], score[1], score[2], team])
res = sorted(res)
res.reverse()
nw = []
for i in range(n // 2):
	nw.append(res[i][3])
nw = sorted(nw)
print(*nw, sep='\n')


(dic, lista, final) = ({}, [], [])
n = int(input())
for i in range(n):
	dic[input()] = {'points': 0, 'scored': 0, 'missed': 0}
matches = [input().split() for j in range(int(n * (n - 1) / 2))]
for j in range(len(matches)):
	(goals1, goals2) = (int(matches[j][1].split(':')[0]), int(matches[j][1].split(':')[1]))
	(team1, team2) = (matches[j][0].split('-')[0], matches[j][0].split('-')[1])
	dic[team1]['scored'] += goals1
	dic[team1]['missed'] += goals2
	dic[team2]['scored'] += goals2
	dic[team2]['missed'] += goals1
	if goals1 > goals2:
		dic[team1]['points'] += 3
	elif goals1 < goals2:
		dic[team2]['points'] += 3
	else:
		dic[team1]['points'] += 1
		dic[team2]['points'] += 1
for i in dic:
	lista.append([dic[i]['points'], dic[i]['scored'] - dic[i]['missed'], dic[i]['scored'], i])
lista = sorted(lista)[::-1]
for i in range(int(n / 2)):
	final.append(lista[i][3])
final = sorted(final)
for i in final:
	print(i)


class Info:

	def __init__(self, newTeamName, newPoints, newGoalDiff, newScoaredGoals):
		self.teamName = newTeamName
		self.points = newPoints
		self.goalDiff = newGoalDiff
		self.scoaredGoals = newScoaredGoals

def indexOfByTeamName(cont, searchName):
	for i in range(len(cont)):
		if cont[i].teamName == searchName:
			return i
	return -1
N = int(input())
cont = []
for i in range(N):
	cont.append(Info(input(), 0, 0, 0))
for i in range(N * (N - 1) // 2):
	s = input()
	dashIndex = s.index('-')
	spaceIndex = s.index(' ')
	colonIndex = s.index(':')
	team1Name = s[0:dashIndex]
	team2Name = s[dashIndex + 1:spaceIndex]
	goal1 = int(s[spaceIndex + 1:colonIndex])
	goal2 = int(s[colonIndex + 1:])
	team1Index = indexOfByTeamName(cont, team1Name)
	team2Index = indexOfByTeamName(cont, team2Name)
	if goal1 > goal2:
		cont[team1Index].points += 3
	elif goal2 > goal1:
		cont[team2Index].points += 3
	else:
		cont[team1Index].points += 1
		cont[team2Index].points += 1
	cont[team1Index].goalDiff += goal1 - goal2
	cont[team2Index].goalDiff += goal2 - goal1
	cont[team1Index].scoaredGoals += goal1
	cont[team2Index].scoaredGoals += goal2
cont.sort(key=lambda item: (item.points, item.goalDiff, item.scoaredGoals), reverse=True)
del cont[N // 2:]
cont.sort(key=lambda item: item.teamName)
for item in cont:
	print(item.teamName)


def addv(vcr, dcntvn, cn, gr, dp, cp):
	if cn not in dcntvn:
		dcntvn[cn] = len(vcr)
		vcr.append([0, 0, 0, cn])
	ind = dcntvn[cn]
	vcr[ind][0] += gr
	vcr[ind][1] += dp
	vcr[ind][2] += cp

def ggr(fcp, scp):
	if fcp > scp:
		return 3
	elif fcp == scp:
		return 1
	else:
		return 0

def gsp(vcr, dcntvn, s):
	fm = s.find('-')
	fcn = s[:fm]
	sm = s.find(' ', fm)
	scn = s[fm + 1:sm]
	fm = s.find(':', sm)
	fcp = int(s[sm + 1:fm])
	scp = int(s[fm + 1:])
	addv(vcr, dcntvn, fcn, ggr(fcp, scp), fcp - scp, fcp)
	addv(vcr, dcntvn, scn, ggr(scp, fcp), scp - fcp, scp)
n = int(input())
vcr = []
dcntvn = dict()
for c in range(n):
	input()
for c in range(n * (n - 1) // 2):
	gsp(vcr, dcntvn, input())
vcr.sort(key=lambda x: (-x[0], -x[1], -x[2]))
wns = vcr[:n // 2]
wns.sort(key=lambda x: x[3])
for c in wns:
	print(c[3])


n = int(input())
team = dict()
for i in range(n):
	team[input()] = [0, 0, 0]
for i in range(n * (n - 1) // 2):
	(a, b) = input().split()
	(t1, t2) = a.split('-')
	(g1, g2) = map(int, b.split(':'))
	team[t1][2] += g1
	team[t2][2] += g2
	if g1 > g2:
		team[t1][0] += 3
	elif g2 > g1:
		team[t2][0] += 3
	else:
		team[t1][0] += 1
		team[t2][0] += 1
	team[t1][1] += g1 - g2
	team[t2][1] += g2 - g1
te = []
for i in team.keys():
	te.append([i, team[i][0], team[i][1], team[i][2]])
for j in range(n):
	for i in range(n - 1 - j):
		if te[i][1] > te[i + 1][1]:
			(te[i], te[i + 1]) = (te[i + 1], te[i])
		elif te[i][1] == te[i + 1][1]:
			if te[i][2] > te[i + 1][2]:
				(te[i], te[i + 1]) = (te[i + 1], te[i])
			elif te[i][2] == te[i + 1][2]:
				if te[i][3] > te[i + 1][3]:
					(te[i], te[i + 1]) = (te[i + 1], te[i])
res = []
for i in range(n - 1, n // 2 - 1, -1):
	res.append(te[i][0])
res.sort()
for i in range(n // 2):
	print(res[i])


n = int(input())
teams_dic = {}
(Points, ScorMiss, Scor) = ('points', 'scored-missed', 'scored goals')
for i in range(n):
	name = input()
	teams_dic[name] = {Points: 0, ScorMiss: 0, Scor: 0}
num_matches = n * (n - 1) // 2
for match in range(num_matches):
	(names, score) = input().split()
	(team1, team2) = names.split('-')
	(score1, score2) = list(map(int, score.split(':')))
	if score1 > score2:
		teams_dic[team1][Points] += 3
	elif score1 == score2:
		teams_dic[team1][Points] += 1
		teams_dic[team2][Points] += 1
	else:
		teams_dic[team2][Points] += 3
	teams_dic[team1][ScorMiss] += score1 - score2
	teams_dic[team2][ScorMiss] += score2 - score1
	teams_dic[team1][Scor] += score1
	teams_dic[team2][Scor] += score2
rank_lst = sorted(teams_dic.keys(), key=lambda team: tuple(teams_dic[team].values()))
qualified = rank_lst[-n // 2:]
qualified = sorted(qualified)
for team in qualified:
	print(team)


n = int(input())
names = list()
score = dict()
goals = dict()
missed = dict()
for i in range(n):
	names.append(input())
	score[names[i]] = 0
	goals[names[i]] = 0
	missed[names[i]] = 0
for i in range(n * (n - 1) // 2):
	(names_h, scores) = input().split(' ')
	(name1, name2) = names_h.split('-')
	(num1, num2) = [int(b) for b in scores.split(':')]
	if num1 == num2:
		score[name1] += 1
		score[name2] += 1
	elif num1 > num2:
		score[name1] += 3
	elif num2 > num1:
		score[name2] += 3
	goals[name1] += num1
	goals[name2] += num2
	missed[name1] += num2
	missed[name2] += num1
diff = dict()
for i in range(n):
	diff[names[i]] = goals[names[i]] - missed[names[i]]
for i in range(n, 0, -1):
	for j in range(1, i):
		if score[names[j]] < score[names[j - 1]]:
			(names[j], names[j - 1]) = (names[j - 1], names[j])
for i in range(n, 0, -1):
	for j in range(1, i):
		if score[names[j]] == score[names[j - 1]]:
			if diff[names[j]] < diff[names[j - 1]]:
				(names[j], names[j - 1]) = (names[j - 1], names[j])
for i in range(n, 0, -1):
	for j in range(1, i):
		if score[names[j]] == score[names[j - 1]]:
			if diff[names[j]] == diff[names[j - 1]]:
				if goals[names[j]] < goals[names[j - 1]]:
					(names[j], names[j - 1]) = (names[j - 1], names[j])
names.reverse()
for i in range(n - 1, n // 2 - 1, -1):
	names.pop(i)
names.sort()
for i in range(len(names)):
	print(names[i])


n = int(input())
comm = {}
for i in range(n):
	comm[input()] = [0] * 3
for i in range(n * (n - 1) // 2):
	(names, scores) = input().split()
	k = names.find('-')
	name1 = names[:k]
	name2 = names[k + 1:]
	k = scores.find(':')
	score1 = int(scores[:k])
	score2 = int(scores[k + 1:])
	comm[name1][2] += score1
	comm[name2][2] += score2
	comm[name1][1] += score1 - score2
	comm[name2][1] += score2 - score1
	if score1 > score2:
		comm[name1][0] += 3
	elif score2 > score1:
		comm[name2][0] += 3
	else:
		comm[name1][0] += 1
		comm[name2][0] += 1
rez = [v[0] for v in sorted(comm.items(), key=lambda x: x[1], reverse=True)][:n // 2]
rez.sort()
for i in rez:
	print(i)


from collections import defaultdict
n = int(input())
ranked = []
for _ in range(n):
	ranked.append(input())
points = defaultdict(int)
goal_diff = defaultdict(int)
goals_scored = defaultdict(int)
for _ in range(int(n * (n - 1) / 2)):
	lst = input().split()
	matchup = lst[0]
	scores = lst[1]
	teams = matchup.split('-')
	first_team = teams[0]
	second_team = teams[1]
	matchup_scores = [int(score) for score in scores.split(':')]
	if first_team not in points:
		points[first_team] = 0
	if second_team not in points:
		points[second_team] = 0
	if first_team not in goal_diff:
		goal_diff[first_team] = 0
	if second_team not in goal_diff:
		goal_diff[second_team] = 0
	if first_team not in goals_scored:
		goals_scored[first_team] = 0
	if second_team not in goals_scored:
		goals_scored[second_team] = 0
	goals_scored[first_team] += matchup_scores[0]
	goals_scored[second_team] += matchup_scores[1]
	goal_diff[first_team] += matchup_scores[0] - matchup_scores[1]
	goal_diff[second_team] += matchup_scores[1] - matchup_scores[0]
	if matchup_scores[0] > matchup_scores[1]:
		points[first_team] += 3
	if matchup_scores[1] > matchup_scores[0]:
		points[second_team] += 3
	if matchup_scores[1] == matchup_scores[0]:
		points[first_team] += 1
		points[second_team] += 1
ranked.sort(key=lambda x: (points[x], goal_diff[x], goals_scored[x]), reverse=True)
for t in sorted(ranked[:int(n / 2)]):
	print(t)


n = int(input())
d = {}
for i in range(n):
	s = str(input())
	d[s] = [0, 0, 0]
for i in range(n * (n - 1) // 2):
	(teams, results) = map(str, input().split(' '))
	(a, b) = map(str, teams.split('-'))
	(c, e) = map(int, results.split(':'))
	d[a][1] += c
	d[a][2] += e
	d[b][1] += e
	d[b][2] += c
	if c == e:
		d[a][0] += 1
		d[b][0] += 1
	elif c > e:
		d[a][0] += 3
	else:
		d[b][0] += 3
for key in d.keys():
	(d[key][1], d[key][2]) = (d[key][1] - d[key][2], d[key][1])
p = set()
for i in sorted(d.items(), key=lambda x: x[1], reverse=True)[:n // 2]:
	p.add(i[0])
for i in sorted(p):
	print(i)


class Info:

	def __init__(self, new_team_name, new_points, new_goal_diff, new_scored_goals):
		self.team_name = new_team_name
		self.points = new_points
		self.goal_diff = new_goal_diff
		self.scored_goals = new_scored_goals

def findIndexByName(cont, search_name):
	for i in range(len(cont)):
		if cont[i].team_name == search_name:
			return i
	return -1
n = int(input())
cont = list()
for i in range(n):
	cont.append(Info(input(), 0, 0, 0))
for i in range(n * (n - 1) // 2):
	s = input()
	dash_index = s.index('-')
	space_index = s.index(' ')
	colon_index = s.index(':')
	team1_name = s[:dash_index]
	team2_name = s[dash_index + 1:space_index]
	goal1 = int(s[space_index + 1:colon_index])
	goal2 = int(s[colon_index + 1:])
	team1_index = findIndexByName(cont, team1_name)
	team2_index = findIndexByName(cont, team2_name)
	if goal1 > goal2:
		cont[team1_index].points += 3
	elif goal2 > goal1:
		cont[team2_index].points += 3
	else:
		cont[team1_index].points += 1
		cont[team2_index].points += 1
	cont[team1_index].goal_diff += goal1 - goal2
	cont[team2_index].goal_diff += goal2 - goal1
	cont[team1_index].scored_goals += goal1
	cont[team2_index].scored_goals += goal2
cont.sort(key=lambda item: (item.points, item.goal_diff, item.scored_goals), reverse=True)
del cont[n // 2:]
cont.sort(key=lambda item: item.team_name)
for item in cont:
	print(item.team_name)


n = int(input())
meeskonnad = [[0, 0, 0, 0, 0, ''] for x in range(n)]
nimed = []
for x in range(n):
	meeskonnad[x][5] = input()
	nimed.append(meeskonnad[x][5])
for x in range(n * (n - 1) // 2):
	s = input()
	r1 = s[:s.find('-')]
	s = s[s.find('-') + 1:]
	r2 = s[:s.find(' ')]
	s = s[s.find(' '):]
	(p1, p2) = map(int, s.split(':'))
	if p1 > p2:
		meeskonnad[nimed.index(r1)][1] -= 1
		meeskonnad[nimed.index(r1)][0] -= 3
	elif p1 < p2:
		meeskonnad[nimed.index(r2)][1] -= 1
		meeskonnad[nimed.index(r2)][0] -= 3
	else:
		meeskonnad[nimed.index(r1)][0] -= 1
		meeskonnad[nimed.index(r2)][0] -= 1
	meeskonnad[nimed.index(r1)][2] -= p1 - p2
	meeskonnad[nimed.index(r2)][2] -= p2 - p1
	meeskonnad[nimed.index(r1)][3] -= p1
	meeskonnad[nimed.index(r2)][3] -= p2
	meeskonnad[nimed.index(r1)][4] += 1
	meeskonnad[nimed.index(r2)][4] += 1
vastus = []
cnt = 0
for x in sorted(meeskonnad, key=lambda i: (i[0], i[1], i[2], i[3], i[4], i[5].upper())):
	cnt += 1
	vastus.append(x[5])
	if cnt * 2 >= n:
		break
print('\n'.join(sorted(vastus)))


class Info:

	def __init__(self, newTeamName, newPoints, newGoalDiff, newScoredGoals):
		self.teamName = newTeamName
		self.points = newPoints
		self.goalDiff = newGoalDiff
		self.scoredGoals = newScoredGoals

	def printData(self):
		print('\n***********************')
		print('teamName: {}'.format(self.teamName))
		print('points: {}'.format(self.points))
		print('goal difference: {}'.format(self.goalDiff))
		print('scored goals: {}'.format(self.scoredGoals))
		print('***********************')

def output(cont: list):
	for item in cont:
		item.printData()

def findIndexByName(cont: list, searchName: str) -> int:
	for i in range(len(cont)):
		if cont[i].teamName == searchName:
			return i
	return -1
cont = []
n = int(input())
for i in range(n):
	cont.append(Info(input(), 0, 0, 0))
for i in range(n * (n - 1) // 2):
	s = input()
	dashInd = s.index('-')
	spaceInd = s.index(' ')
	colonInd = s.index(':')
	team1Name = s[0:dashInd]
	team2Name = s[dashInd + 1:spaceInd]
	goal1 = int(s[spaceInd + 1:colonInd])
	goal2 = int(s[colonInd + 1:])
	team1Index = findIndexByName(cont, team1Name)
	team2Index = findIndexByName(cont, team2Name)
	if goal1 > goal2:
		cont[team1Index].points += 3
	elif goal2 > goal1:
		cont[team2Index].points += 3
	else:
		cont[team1Index].points += 1
		cont[team2Index].points += 1
	cont[team1Index].goalDiff += goal1 - goal2
	cont[team2Index].goalDiff += goal2 - goal1
	cont[team1Index].scoredGoals += goal1
	cont[team2Index].scoredGoals += goal2
cont.sort(key=lambda item: (item.points, item.goalDiff, item.scoredGoals), reverse=True)
del cont[n // 2:]
cont.sort(key=lambda item: item.teamName)
for item in cont:
	print(item.teamName)


class Info:

	def __init__(self, newTeamName, newPoints, newGoalDiff, newScoredGoals):
		self.teamName = newTeamName
		self.points = newPoints
		self.goalDiff = newGoalDiff
		self.scoredGoals = newScoredGoals

	def __str__(self):
		temp = '\n**************\n'
		temp += f'teamName: {self.teamName} \n'
		temp += f'points: {self.points} \n'
		temp += f'goalDiff: {self.goalDiff} \n'
		temp += f'scoredGoals: {self.scoredGoals} \n'
		temp += '**************\n'
		return temp

def findIndexByName(cont: list, searchName: str) -> int:
	ln = len(cont)
	for i in range(ln):
		if searchName == cont[i].teamName:
			return i
	return -1

def output(cont: list):
	for item in cont:
		print(item)
(n, cont) = (int(input()), [])
for i in range(n):
	cont.append(Info(input(), 0, 0, 0))
for i in range(n * (n - 1) // 2):
	line = input()
	dashInd = line.index('-')
	spaceInd = line.index(' ')
	colonInd = line.index(':')
	team1Name = line[:dashInd]
	team2Name = line[dashInd + 1:spaceInd]
	score1 = int(line[spaceInd + 1:colonInd])
	score2 = int(line[colonInd + 1:])
	team1Ind = findIndexByName(cont, team1Name)
	team2Ind = findIndexByName(cont, team2Name)
	if score1 > score2:
		cont[team1Ind].points += 3
	elif score1 < score2:
		cont[team2Ind].points += 3
	else:
		cont[team1Ind].points += 1
		cont[team2Ind].points += 1
	cont[team1Ind].goalDiff += score1 - score2
	cont[team2Ind].goalDiff += score2 - score1
	cont[team1Ind].scoredGoals += score1
	cont[team2Ind].scoredGoals += score2
cont.sort(key=lambda it: (it.points, it.goalDiff, it.scoredGoals), reverse=True)
del cont[n // 2:]
cont.sort(key=lambda it: it.teamName)
for item in cont:
	print(item.teamName)


n = int(input())
res = {input(): [0, 0, 0] for i in range(n)}
for i in range(n * (n - 1) // 2):
	(teams, score) = input().split()
	(team1, team2) = teams.split('-')
	(sc1, sc2) = map(int, score.split(':'))
	if sc1 > sc2:
		res[team1][0] += 3
	elif sc2 > sc1:
		res[team2][0] += 3
	else:
		res[team1][0] += 1
		res[team2][0] += 1
	res[team1][1] += sc1 - sc2
	res[team2][1] += sc2 - sc1
	res[team1][2] += sc1
	res[team2][2] += sc2
table = sorted(((res[key], key) for key in res), reverse=True)
print('\n'.join(sorted([row[1] for row in table[:n // 2]])))


class Team:

	def __init__(self, team_name):
		self.team_name = team_name
		self.points = 0
		self.dif = 0
		self.score = 0

	def get_result(self, scr, allowed):
		self.score += scr
		self.dif += scr - allowed
		if scr > allowed:
			self.points += 3
		elif scr == allowed:
			self.points += 1

	def display(self):
		print(f'{self.team_name}\t{self.points}\t{self.dif}\t{self.score}')

	def comp(self, team2):
		if self.points < team2.points:
			return True
		elif self.points == team2.points and self.dif < team2.dif:
			return True
		elif self.points == team2.points and self.dif == team2.dif and (self.score < team2.score):
			return True
		else:
			return False
result = {}
list_team = []
n = int(input())
for i in range(n):
	name = input()
	t = Team(name)
	list_team.append(t)
num_of_matches = n * (n - 1) // 2
for match in range(num_of_matches):
	inp = input()
	versus = inp.split()
	result[versus[0]] = versus[1]
start = 0
for (order, game) in result.items():
	vs = order.split('-')
	res = game.split(':')
	for t1 in range(len(list_team)):
		if list_team[t1].team_name == vs[0]:
			list_team[t1].get_result(int(res[0]), int(res[1]))
		if list_team[t1].team_name == vs[1]:
			list_team[t1].get_result(int(res[1]), int(res[0]))
for i in range(len(list_team) - 1):
	for j in range(i + 1, len(list_team)):
		if list_team[i].comp(list_team[j]):
			(list_team[i], list_team[j]) = (list_team[j], list_team[i])
tname = []
for i in range(len(list_team) // 2):
	tname.append(list_team[i].team_name)
tname = sorted(tname)
for i in range(len(tname)):
	print(tname[i])


class Info:

	def __init__(self, _new_team_name, _new_points, _new_goal_diff, _new_scored_goals):
		self.team_name = _new_team_name
		self.points = _new_points
		self.goal_diff = _new_goal_diff
		self.scored_goals = _new_scored_goals

def findIndexByTeamName(container, search_team_name):
	for (indx, item) in enumerate(container):
		if item.team_name == search_team_name:
			return indx
	return -1
(n, cont) = (int(input()), list())
for i in range(n):
	cont.append(Info(input(), 0, 0, 0))
for i in range(n * (n - 1) // 2):
	s = input()
	dash_index = s.index('-')
	space_index = s.index(' ')
	colon_index = s.index(':')
	team1_name = s[0:dash_index]
	team2_name = s[dash_index + 1:space_index]
	goal1 = int(s[space_index + 1:colon_index])
	goal2 = int(s[colon_index + 1:])
	team1_index = findIndexByTeamName(cont, team1_name)
	team2_index = findIndexByTeamName(cont, team2_name)
	if goal1 > goal2:
		cont[team1_index].points += 3
	elif goal1 < goal2:
		cont[team2_index].points += 3
	else:
		cont[team1_index].points += 1
		cont[team2_index].points += 1
	cont[team1_index].goal_diff += goal1 - goal2
	cont[team2_index].goal_diff += goal2 - goal1
	cont[team1_index].scored_goals += goal1
	cont[team2_index].scored_goals += goal2
cont.sort(key=lambda item: (item.points, item.goal_diff, item.scored_goals), reverse=True)
del cont[n // 2:]
cont.sort(key=lambda item: item.team_name)
for item in cont:
	print(item.team_name)


n = int(input())
a1 = []
a2 = []
a3 = []
a4 = []
a5 = [0] * n
a6 = []
ac = []
goles = 0
puntos = 0
mayor = 0
yonax = 0
carol = 0
contador = 0
contras = 0
for k in range(n):
	x = input()
	a1.append(x)
for l in range((n - 1) * n // 2):
	b = input()
	b = b.partition(' ')
	co = b[0].partition('-')
	du = b[2].partition(':')
	b = co[0] + ' ' + co[1] + ' ' + co[2] + ' ' + 'j' + ' ' + du[0] + ' ' + du[1] + ' ' + du[2]
	b = b.split()
	a2.append(b)
for a in range(n):
	for b in range(len(a2)):
		for c in range(3):
			if a1[a] == a2[b][c]:
				if c == 0:
					goles = goles + int(a2[b][4])
					goles = goles - int(a2[b][6])
				if c == 2:
					goles = goles + int(a2[b][6])
					goles = goles - int(a2[b][4])
	a3.append(goles)
	goles = 0
for carito in range(n):
	for alexita in range(len(a2)):
		for kamila in range(3):
			if a1[carito] == a2[alexita][kamila]:
				if kamila == 0:
					contras = contras + int(a2[alexita][6])
				if kamila == 2:
					contras = contras + int(a2[alexita][4])
	ac.append(contras)
	contras = 0
for d in range(n):
	for e in range(len(a2)):
		for f in range(3):
			if a1[d] == a2[e][f]:
				if f == 0:
					if int(a2[e][4]) > int(a2[e][6]):
						puntos = puntos + 3
					if int(a2[e][4]) == int(a2[e][6]):
						puntos = puntos + 1
				if f == 2:
					if int(a2[e][6]) > int(a2[e][4]):
						puntos = puntos + 3
					if int(a2[e][6]) == int(a2[e][4]):
						puntos = puntos + 1
	a4.append(puntos)
	puntos = 0
for g in range(n):
	for h in range(n):
		carol = carol + 1
		if int(a4[g]) > int(a4[h]):
			mayor = mayor + 1
		if int(a4[g]) == int(a4[h]):
			if int(a3[g]) > int(a3[h]):
				mayor = mayor + 1
			if int(a3[g]) == int(a3[h]):
				if int(ac[g]) > int(ac[h]):
					mayor = mayor + 1
				if a3[g] == int(a3[h]):
					mayor = mayor
					yonax = 8
					k = k + 1
	pame = (k - n) ** (1 // 2)
	po = n - mayor - 1
	mayor = 0
	if po > 0 and a5[po - 1] == 0:
		a5[po - pame] = a1[g]
	a5[po] = a1[g]
for la in range(n // 2):
	a6.append(a5[la])
a6.sort()
for yonax in range(len(a6)):
	print(a6[yonax])


score = {}
n = int(input())
for i in range(n):
	team = input()
	score[team] = [0, 0, 0]
for i in range(n * (n - 1) // 2):
	s = input().split()
	teams = s[0].split('-')
	first = teams[0]
	second = teams[1]
	scores = s[1].split(':')
	first_score = int(scores[0])
	second_score = int(scores[1])
	if first_score < second_score:
		score[second][0] += 3
		score[second][1] = score[second][1] + second_score - first_score
		score[second][2] += second_score
		score[first][1] = score[first][1] + first_score - second_score
		score[first][2] += first_score
	if first_score > second_score:
		score[first][0] += 3
		score[first][1] += first_score - second_score
		score[first][2] += first_score
		score[second][1] += second_score - first_score
		score[second][2] += second_score
	elif first_score == second_score:
		score[first][0] += 1
		score[first][1] += first_score - second_score
		score[first][2] += first_score
		score[second][0] += 1
		score[second][1] += second_score - first_score
		score[second][2] += second_score
results = []
for (team, score) in score.items():
	results.append([score[0], score[1], score[2], team])
results = sorted(results)
results.reverse()
nw = []
for i in range(n // 2):
	nw.append(results[i][3])
nw = sorted(nw)
print(*nw, sep='\n')


import math
n = int(input())
d = {}
for i in range(n):
	d[input()] = [0, 0, 0]
for i in range(math.factorial(n) // (2 * math.factorial(n - 2))):
	(t, s) = input().split()
	(t1, t2) = t.split('-')
	(s1, s2) = map(int, s.split(':'))
	if s1 > s2:
		d[t1][0] += 3
		d[t1][1] += abs(s1 - s2)
		d[t2][1] -= abs(s1 - s2)
	elif s1 == s2:
		d[t1][0] += 1
		d[t2][0] += 1
	else:
		d[t2][0] += 3
		d[t1][1] -= abs(s1 - s2)
		d[t2][1] += abs(s1 - s2)
	d[t1][2] += s1
	d[t1][2] += s2
print(*sorted(sorted(d.keys(), key=lambda xx: (-d[xx][0], -d[xx][1], -d[xx][2]))[:n // 2]), sep='\n')


n = int(input())

class Command:

	def __init__(self, name):
		self.name = name
		self.score = 0
		self.z = 0
		self.p = 0

	def get_r(self):
		return self.z - self.p
arr = {}
for i in range(n):
	name = input()
	arr[name] = Command(name)
for i in range(n * (n - 1) // 2):
	string = input()
	(first, second) = string.split()
	(name1, name2) = first.split('-')
	(num1, num2) = second.split(':')
	(num1, num2) = (int(num1), int(num2))
	if num1 > num2:
		arr[name1].score += 3
	elif num1 < num2:
		arr[name2].score += 3
	else:
		arr[name1].score += 1
		arr[name2].score += 1
	arr[name1].z += num1
	arr[name1].p += num2
	arr[name2].z += num2
	arr[name2].p += num1
arr = list(arr.values())
for i in range(len(arr)):
	for j in range(len(arr) - 1):
		if arr[j].score < arr[j + 1].score:
			(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		elif arr[j].score == arr[j + 1].score:
			if arr[j].get_r() < arr[j + 1].get_r():
				(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
			elif arr[j].get_r() == arr[j + 1].get_r():
				if arr[j].z < arr[j + 1].z:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
ans = []
for i in range(len(arr) // 2):
	ans.append(arr[i].name)
ans.sort()
for i in ans:
	print(i)


class Info:

	def __init__(self, newTeamName, newPoints, newGoalDiff, newScoredGoals):
		self.teamName = newTeamName
		self.points = newPoints
		self.goalDiff = newGoalDiff
		self.scoredGoals = newScoredGoals

def findIndexByName(cont, searchName):
	for i in range(len(cont)):
		if cont[i].teamName == searchName:
			return i
	return -1
n = int(input())
cont = []
for i in range(n):
	cont.append(Info(input(), 0, 0, 0))
for i in range(n * (n - 1) // 2):
	s = input()
	dashInd = s.index('-')
	spaceInd = s.index(' ')
	colonInd = s.index(':')
	team1Name = s[0:dashInd]
	team2Name = s[dashInd + 1:spaceInd]
	goal1 = int(s[spaceInd + 1:colonInd])
	goal2 = int(s[colonInd + 1:])
	team1Ind = findIndexByName(cont, team1Name)
	team2Ind = findIndexByName(cont, team2Name)
	if goal1 > goal2:
		cont[team1Ind].points += 3
	elif goal1 < goal2:
		cont[team2Ind].points += 3
	else:
		cont[team1Ind].points += 1
		cont[team2Ind].points += 1
	cont[team1Ind].goalDiff += goal1 - goal2
	cont[team2Ind].goalDiff += goal2 - goal1
	cont[team1Ind].scoredGoals += goal1
cont.sort(key=lambda item: (item.points, item.goalDiff, item.scoredGoals), reverse=True)
del cont[n // 2:]
cont.sort(key=lambda item: item.teamName)
for item in cont:
	print(item.teamName)


number = int(input())
d = dict()
for i in range(number):
	d[input()] = [0, 0, 0]
for i in range(number * (number - 1) // 2):
	(t, s) = input().split()
	(team1, team2) = t.split('-')
	(score1, score2) = [int(x) for x in s.split(':')]
	a = d[team1]
	b = d[team2]
	a[2] += score1
	b[2] += score2
	a[1] += score1 - score2
	b[1] += score2 - score1
	if score1 == score2:
		a[0] += 1
		b[0] += 1
	elif score1 < score2:
		b[0] += 3
	else:
		a[0] += 3
printedscore = (b for (a, b) in sorted(((b, a) for (a, b) in d.items()))[number // 2:])
print('\n'.join(sorted(printedscore)))


class Info:

	def __init__(self, _team_name, _points, _goal_diff, _scored_goals):
		self.TeamName = _team_name
		self.Points = _points
		self.GoalDiff = _goal_diff
		self.ScoredGoals = _scored_goals

def findIndexByName(container, _team_name):
	for (indx, item) in enumerate(container):
		if item.TeamName == _team_name:
			return indx
	return -1
n = int(input())
cont = []
for i in range(n):
	cont.append(Info(input(), 0, 0, 0))
for i in range(n * (n - 1) // 2):
	s = input()
	dashIndex = s.index('-')
	spaceIndex = s.index(' ')
	colonIndex = s.index(':')
	team1Name = s[0:dashIndex]
	team2Name = s[dashIndex + 1:spaceIndex]
	goal1 = int(s[spaceIndex + 1:colonIndex])
	goal2 = int(s[colonIndex + 1:])
	team1Index = findIndexByName(cont, team1Name)
	team2Index = findIndexByName(cont, team2Name)
	if goal1 > goal2:
		cont[team1Index].Points += 3
	elif goal1 < goal2:
		cont[team2Index].Points += 3
	else:
		cont[team1Index].Points += 1
		cont[team2Index].Points += 1
	cont[team1Index].GoalDiff += goal1 - goal2
	cont[team2Index].GoalDiff += goal2 - goal1
	cont[team1Index].ScoredGoals += goal1
	cont[team2Index].ScoredGoals += goal2
cont.sort(key=lambda item: (item.Points, item.GoalDiff, item.ScoredGoals), reverse=True)
del cont[n // 2:]
cont.sort(key=lambda item: item.TeamName)
for item in cont:
	print(item.TeamName)


n = int(input())
s = []
bal = dict()
g_zab = dict()
g_pr = dict()
k = 0
for i in range(1, n):
	k = k + i
for i in range(n):
	c = input()
	s.append(c)
for i in range(k):
	(a1, b1) = input().split()
	(k1, k2) = a1.split('-')
	(c1, c2) = b1.split(':')
	c1 = int(c1)
	c2 = int(c2)
	if k1 in g_zab:
		g_zab[k1] = g_zab.get(k1) + c1
	else:
		g_zab[k1] = c1
	if k2 in g_zab:
		g_zab[k2] = g_zab.get(k2) + c2
	else:
		g_zab[k2] = c2
	if k1 in g_pr:
		g_pr[k1] = g_pr.get(k1) + c2
	else:
		g_pr[k1] = c2
	if k2 in g_pr:
		g_pr[k2] = g_pr.get(k2) + c1
	else:
		g_pr[k2] = c1
	if c1 == c2:
		if k1 in bal:
			bal[k1] = bal.get(k1) + 1
		else:
			bal[k1] = 1
		if k2 in bal:
			bal[k2] = bal.get(k2) + 1
		else:
			bal[k2] = 1
	elif c1 > c2:
		if k1 in bal:
			bal[k1] = bal.get(k1) + 3
		else:
			bal[k1] = 3
		if k2 in bal:
			bal[k2] = bal.get(k2) + 0
		else:
			bal[k2] = 0
	else:
		if k2 in bal:
			bal[k2] = bal.get(k2) + 3
		else:
			bal[k2] = 3
		if k1 in bal:
			bal[k1] = bal.get(k1) + 0
		else:
			bal[k1] = 0
spisok = []
for name in s:
	ch = bal[name]
	razn = g_zab[name] - g_pr[name]
	zab = g_zab[name]
	ss = [ch, razn, zab, name]
	spisok.append(ss)
spisok = sorted(spisok)
spisok = spisok[int(n / 2):]
com = [e[3] for e in spisok]
com = sorted(com)
for e in com:
	print(e)


from operator import itemgetter
n = int(input())
_T = []
T = []
Z = []
for i in range(n):
	q = input()
	_T.append(q)
	T.append([q, 0, 0, 0])
for i in range(int(n * (n - 1) / 2)):
	c = list(map(str, input().split(' ')))
	(t1, t2) = list(map(str, c[0].split('-')))
	(s1, s2) = list(map(int, c[1].split(':')))
	i1 = _T.index(t1)
	i2 = _T.index(t2)
	if s1 > s2:
		T[i1][1] += 3
	if s2 > s1:
		T[i2][1] += 3
	if s2 == s1:
		T[i1][1] += 1
		T[i2][1] += 1
	T[i1][2] += s1 - s2
	T[i2][2] += s2 - s1
	T[i1][3] += s1
	T[i2][3] += s2
T.sort(key=itemgetter(1, 2, 3), reverse=True)
for t in T[:int(n / 2)]:
	Z.append(t[0])
Z.sort()
print('\n'.join(Z))


class Info:

	def __init__(self, _team_name, _points, _goal_diff, _scored_goals):
		self.TeamName = _team_name
		self.Points = _points
		self.GoalDiff = _goal_diff
		self.ScoredGoals = _scored_goals

def findIndexByTeamName(container, team_name):
	for (ind, item) in enumerate(container):
		if item.TeamName == team_name:
			return ind
	return -1
N = int(input())
cont = list()
for i in range(N):
	cont.append(Info(input(), 0, 0, 0))
for i in range(N * (N - 1) // 2):
	s = input()
	dashIndex = s.index('-')
	spaceIndex = s.index(' ')
	colonIndex = s.index(':')
	Team1Name = s[0:dashIndex]
	Team2Name = s[dashIndex + 1:spaceIndex]
	Goal1 = int(s[spaceIndex + 1:colonIndex])
	Goal2 = int(s[colonIndex + 1:])
	Team1Index = findIndexByTeamName(cont, Team1Name)
	Team2Index = findIndexByTeamName(cont, Team2Name)
	if Goal1 > Goal2:
		cont[Team1Index].Points += 3
	elif Goal1 < Goal2:
		cont[Team2Index].Points += 3
	else:
		cont[Team1Index].Points += 1
		cont[Team2Index].Points += 1
	cont[Team1Index].GoalDiff += Goal1 - Goal2
	cont[Team2Index].GoalDiff += Goal2 - Goal1
	cont[Team1Index].ScoredGoals += Goal1
	cont[Team2Index].ScoredGoals += Goal2
cont.sort(key=lambda item: (item.Points, item.GoalDiff, item.ScoredGoals), reverse=True)
del cont[N // 2:]
cont.sort(key=lambda item: item.TeamName)
for item in cont:
	print(item.TeamName)


from operator import attrgetter

def completeTeamInfo(team, scored, missed):
	team.scoredGoals += scored
	team.missedGoals += missed
	team.differenceScoredAndMissed += scored - missed
	if scored > missed:
		team.points += 3
	elif scored == missed:
		team.points += 1

def arrangeTeams(totals):
	totals.sort(key=lambda team: (team.points, team.differenceScoredAndMissed, team.scoredGoals), reverse=True)

def main():

	class Team:
		scoredGoals = 0
		missedGoals = 0
		differenceScoredAndMissed = 0
		points = 0

		def __init__(self, name):
			self.name = name
	teamsNr = int(input())
	totals = []
	for _ in range(teamsNr):
		name = input()
		totals.append(Team(name))
	for _ in range(teamsNr * (teamsNr - 1) // 2):
		(playingTeams, score) = input().split()
		teamOne = playingTeams[:playingTeams.index('-')]
		teamTwo = playingTeams[playingTeams.index('-') + 1:]
		scoreTeamOne = int(score[:score.index(':')])
		scoreTeamTwo = int(score[score.index(':') + 1:])
		for team in totals:
			if team.name == teamOne:
				completeTeamInfo(team, scoreTeamOne, scoreTeamTwo)
			if team.name == teamTwo:
				completeTeamInfo(team, scoreTeamTwo, scoreTeamOne)
	arrangeTeams(totals)
	i = 0
	result = []
	while i < teamsNr // 2:
		result.append(totals[i].name)
		i += 1
	result.sort()
	for res in result:
		print(res)
main()


n = int(input())
a = {}
for i in range(n):
	a[input()] = [0, 0, 0]
k = n * (n - 1) // 2
for i in range(k):
	s = input().split(' ')
	(c1, c2) = s[0].split('-')
	(g1, g2) = map(int, s[1].split(':'))
	a[c1] = [a[c1][0], a[c1][1] + (g1 - g2), a[c1][2] + g1]
	a[c2] = [a[c2][0], a[c2][1] + (g2 - g1), a[c2][2] + g2]
	if g1 > g2:
		a[c1][0] += 3
	elif g2 > g1:
		a[c2][0] += 3
	else:
		a[c1][0] += 1
		a[c2][0] += 1
print('\n'.join(sorted((y for (x, y) in sorted(((y, x) for (x, y) in a.items()))[n // 2:]))))


from functools import cmp_to_key
n = int(input())
teams = [input() for _ in range(n)]
sc = dict()
go = dict()
lo = dict()
teams.reverse()
for _ in range(n * (n - 1) // 2):
	s = input().split()
	tm = s[0].split('-')
	score = [int(x) for x in s[1].split(':')]
	if score[0] == score[1]:
		sc[tm[0]] = sc.get(tm[0], 0) + 1
		sc[tm[1]] = sc.get(tm[1], 0) + 1
	if score[0] > score[1]:
		sc[tm[0]] = sc.get(tm[0], 0) + 3
		sc[tm[1]] = sc.get(tm[1], 0) + 0
	if score[1] > score[0]:
		sc[tm[0]] = sc.get(tm[0], 0) + 0
		sc[tm[1]] = sc.get(tm[1], 0) + 3
	go[tm[0]] = go.get(tm[0], 0) + score[0]
	go[tm[1]] = go.get(tm[1], 0) + score[1]
	lo[tm[0]] = lo.get(tm[0], 0) + score[1]
	lo[tm[1]] = lo.get(tm[1], 0) + score[0]

def compare(a, b):
	if sc.get(a, 0) != sc.get(b, 0):
		return sc.get(a, 0) - sc.get(b, 0)
	if go.get(a, 0) - lo.get(a, 0) != go.get(b, 0) - lo.get(b, 0):
		return go.get(a, 0) - lo.get(a, 0) - (go.get(b, 0) - lo.get(b, 0))
	if go.get(a, 0) != go.get(b, 0):
		return go.get(a, 0) - go.get(b, 0)
res = sorted(teams, key=cmp_to_key(compare))[n // 2:n]
for s in sorted(res):
	print(s)


import re
n = int(input())
list = []
for i in range(0, n):
	item = input()
	list.append(item)
list2 = []
for i in range(0, int(n * (n - 1) / 2)):
	item = input()
	list2.append(item)
poi = [int(0)] * n
diff = [int(0)] * n
sco = [int(0)] * n
for i in list2:
	i = re.findall("[\\w']+", i)
	if int(i[2]) > int(i[3]):
		j = list.index(i[0])
		k = list.index(i[1])
		poi[j] = int(poi[j]) + 3
		sco[j] = int(sco[j]) + int(i[2])
		sco[k] = int(sco[k]) + int(i[3])
		diff[j] = int(diff[j]) + int(i[2]) - int(i[3])
		diff[k] = int(diff[k]) + int(i[3]) - int(i[2])
	if int(i[2]) == int(i[3]):
		j = list.index(i[0])
		k = list.index(i[1])
		poi[j] = int(poi[j]) + 1
		poi[k] = int(poi[k]) + 1
		sco[j] = int(sco[j]) + int(i[2])
		sco[k] = int(sco[k]) + int(i[3])
		diff[j] = int(diff[j]) + int(i[2]) - int(i[3])
		diff[k] = int(diff[k]) + int(i[3]) - int(i[2])
	if int(i[2]) < int(i[3]):
		j = list.index(i[0])
		k = list.index(i[1])
		poi[k] = int(poi[k]) + 3
		sco[j] = int(sco[j]) + int(i[2])
		sco[k] = int(sco[k]) + int(i[3])
		diff[j] = int(diff[j]) + int(i[2]) - int(i[3])
		diff[k] = int(diff[k]) + int(i[3]) - int(i[2])
for i in range(0, n):
	for j in range(0, i):
		if poi[i] > poi[j]:
			c = list[i]
			list[i] = list[j]
			list[j] = c
			c = poi[i]
			poi[i] = poi[j]
			poi[j] = c
			c = diff[i]
			diff[i] = diff[j]
			diff[j] = c
			c = sco[i]
			sco[i] = sco[j]
			sco[j] = c
		if poi[i] == poi[j]:
			if diff[i] > diff[j]:
				c = list[i]
				list[i] = list[j]
				list[j] = c
				c = poi[i]
				poi[i] = poi[j]
				poi[j] = c
				c = diff[i]
				diff[i] = diff[j]
				diff[j] = c
				c = sco[i]
				sco[i] = sco[j]
				sco[j] = c
			if diff[i] == diff[j]:
				if sco[i] > sco[j]:
					c = list[i]
					list[i] = list[j]
					list[j] = c
					c = poi[i]
					poi[i] = poi[j]
					poi[j] = c
					c = diff[i]
					diff[i] = diff[j]
					diff[j] = c
					c = sco[i]
					sco[i] = sco[j]
					sco[j] = c
list = sorted(list[0:int(n / 2)])
for i in range(0, int(n / 2)):
	print(list[i])


n = int(input())
teams = dict()
for i in range(n):
	teams[input()] = [0, 0, 0]
for i in range(n * (n - 1) // 2):
	(team, score) = input().split()
	(t1, t2) = team.split('-')
	(s1, s2) = [int(x) for x in score.split(':')]
	a = teams[t1]
	b = teams[t2]
	a[2] += s1
	b[2] += s2
	a[1] += s1 - s2
	b[1] += s2 - s1
	if s1 == s2:
		a[0] += 1
		b[0] += 1
	elif s1 < s2:
		b[0] += 3
	else:
		a[0] += 3
print('\n'.join(sorted((b for (a, b) in sorted(((b, a) for (a, b) in teams.items()))[n // 2:]))))


team_rankings = {}
n = int(input())
for i in range(n):
	team = input()
	team_rankings[team] = [0, 0, 0]
for _ in range(n * (n - 1) // 2):
	data = input().split()
	teams = data[0].split('-')
	team_1 = teams[0]
	team_2 = teams[1]
	scores = data[1].split(':')
	score_t1 = int(scores[0])
	score_t2 = int(scores[1])
	if score_t1 < score_t2:
		team_rankings[team_2][0] += 3
		team_rankings[team_2][1] += score_t2 - score_t1
		team_rankings[team_2][2] += score_t2
		team_rankings[team_1][1] += score_t1 - score_t2
		team_rankings[team_1][2] += score_t1
	if score_t1 > score_t2:
		team_rankings[team_1][0] += 3
		team_rankings[team_1][1] += score_t1 - score_t2
		team_rankings[team_1][2] += score_t1
		team_rankings[team_2][1] += score_t2 - score_t1
		team_rankings[team_2][2] += score_t2
	elif score_t1 == score_t2:
		team_rankings[team_1][0] += 1
		team_rankings[team_1][1] += score_t1 - score_t2
		team_rankings[team_1][2] += score_t1
		team_rankings[team_2][0] += 1
		team_rankings[team_2][1] += score_t2 - score_t1
		team_rankings[team_2][2] += score_t2
results = []
for (team, team_rankings) in team_rankings.items():
	results.append([team_rankings[0], team_rankings[1], team_rankings[2], team])
results = sorted(results)
results.reverse()
qualified = []
for i in range(n // 2):
	qualified.append(results[i][3])
qualified = sorted(qualified)
print(*qualified, sep='\n')


(p, n) = ({}, int(input()))
for i in range(n):
	p[input()] = [0, 0, 0]
for i in range(n * (n - 1) // 2):
	t = input().split()
	(a, b) = t[0].split('-')
	(x, y) = t[1].split(':')
	(x, y) = (int(x), int(y))
	if x > y:
		p[a][0] += 3
	elif x < y:
		p[b][0] += 3
	else:
		p[a][0] += 1
		p[b][0] += 1
	p[a][1] += y
	p[b][1] += x
	p[a][2] += x
	p[b][2] += y
for c in p:
	p[c][1] = p[c][2] - p[c][1]
r = sorted(p.items(), reverse=True, key=lambda x: x[1])
print('\n'.join(sorted((r[i][0] for i in range(n // 2)))))


def completeTeamInfo(team, scored, missed):
	team.scoredGoals += scored
	team.missedGoals += missed
	team.differenceScoredAndMissed += scored - missed
	if scored > missed:
		team.points += 3
	elif scored == missed:
		team.points += 1

def arrangeTeams(totals):
	totals.sort(key=lambda team: (team.points, team.differenceScoredAndMissed, team.scoredGoals), reverse=True)

def main():

	class Team:
		scoredGoals = 0
		missedGoals = 0
		differenceScoredAndMissed = 0
		points = 0

		def __init__(self, name):
			self.name = name
	teamsNr = int(input())
	totals = []
	for _ in range(teamsNr):
		name = input()
		totals.append(Team(name))
	for _ in range(teamsNr * (teamsNr - 1) // 2):
		(playingTeams, score) = input().split()
		teamOne = playingTeams[:playingTeams.index('-')]
		teamTwo = playingTeams[playingTeams.index('-') + 1:]
		scoreTeamOne = int(score[:score.index(':')])
		scoreTeamTwo = int(score[score.index(':') + 1:])
		for team in totals:
			if team.name == teamOne:
				completeTeamInfo(team, scoreTeamOne, scoreTeamTwo)
			if team.name == teamTwo:
				completeTeamInfo(team, scoreTeamTwo, scoreTeamOne)
	arrangeTeams(totals)
	winners = []
	for i in range(teamsNr // 2):
		winners.append(totals[i].name)
	winners.sort()
	for winner in winners:
		print(winner)
main()


n = int(input())
teams = {}
second = {}
third = {}
for _ in range(n):
	a = input()
	teams[a] = 0
	second[a] = 0
	third[a] = 0
no = int((n - 1) * n / 2)
for _ in range(no):
	(a, b) = input().split()
	a = a.split('-')
	b = b.split(':')
	b[0] = int(b[0])
	b[1] = int(b[1])
	if b[0] > b[1]:
		teams[a[0]] = teams[a[0]] + 3
	elif b[0] == b[1]:
		teams[a[1]] = teams[a[1]] + 1
		teams[a[0]] = teams[a[0]] + 1
	else:
		teams[a[1]] = teams[a[1]] + 3
	second[a[0]] = second[a[0]] + (b[0] - b[1])
	second[a[1]] = second[a[1]] + (b[1] - b[0])
	third[a[1]] = third[a[1]] + b[1]
	third[a[0]] = third[a[0]] + b[0]
final = sorted(teams.items(), key=lambda v: (v[1], v[0]))
final.reverse()
for _ in range(n):
	for i in range(n - 1):
		if final[i][1] == final[i + 1][1]:
			if second[final[i][0]] < second[final[i + 1][0]]:
				(final[i], final[i + 1]) = (final[i + 1], final[i])
			elif second[final[i][0]] == second[final[i + 1][0]]:
				if third[final[i][0]] < third[final[i + 1][0]]:
					(final[i], final[i + 1]) = (final[i + 1], final[i])
x = []
for i in range(int(n / 2)):
	x.append(final[i][0])
x.sort()
for i in x:
	print(i)


n = int(input())
teams = {}
for _ in range(n):
	teams[input()] = [0, 0, 0]
for _ in range(n * (n - 1) // 2):
	line = input().split()
	(a, b) = line[0].split('-')
	(x, y) = list(map(int, line[1].split(':')))
	if x > y:
		teams[a][0] += 3
	elif x < y:
		teams[b][0] += 3
	else:
		teams[a][0] += 1
		teams[b][0] += 1
	teams[a][1] += x - y
	teams[a][2] += x
	teams[b][1] += y - x
	teams[b][2] += y
teamsList = []
for team in teams:
	teamsList.append([teams[team], team])
teamsList.sort(reverse=True)
ans = []
for k in range(n // 2):
	ans.append(teamsList[k][1])
ans.sort()
print('\n'.join(ans))