大家都知道2010年世界杯正在南非举行。根据BFA(贝尔兰足球协会)的决定,下一届世界杯将在贝尔兰举行。博鳌亚洲论坛决定修改部分世界杯规则:
- 决赛有 n 支队伍(n 始终为偶数)
- 前n / 2支球队(根据积分榜)进入淘汰赛阶段
- 排名按照以下原则进行:胜队得 3 分,平局得 1 分,负队得 0 分。首先,球队在积分榜上的排名是按照积分从高到低的顺序排列的;第二位——按照进球数和失球数之间的差值降序排列;第三位——按进球数降序排列
- Berland 宪法中写道,之前的规定有助于明确地对团队进行排序。
你被要求编写一个程序,根据给定的参赛球队名单和所有比赛的结果,找到进入淘汰赛阶段的球队名单。
输入
第一个输入行包含唯一的整数 n (1 ≤ n ≤ 50) — 参加世界杯决赛的球队数量。接下来的n行包含了这些球队的名字,名字是一串大小写拉丁字母,长度不超过30个字符。以下 n·(n - 1) / 2 行以 name1-name2 num1:num2 的格式描述所举行的比赛,其中 name1、name2 — 球队名称; num1, num2 (0 ≤ num1, num2 ≤ 100) — 相应球队进球数。保证描述的准确性:没有两个队名与字母大小写完全一致;没有一场比赛是球队与自己比赛;每个匹配项在描述中仅出现一次。
输出
输出 n / 2 行 — 按字典顺序成功进入淘汰赛阶段的球队名称。在单独的行中输出每个名称。不允许出现奇数字符(包括空格)。保证所描述的规则有助于明确地对团队进行排序。
示例
输入 #1
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
输出 #1
A D
输入 #2
2 a A a-A 2:1
输出 #2
a