← 返回题目列表

Codeforces · 659/B

B. 资格赛

中文机器翻译题面 查看原题

Berland 很快将举办学校团队编程奥林匹克竞赛。来自柏林地区的每个地区都会邀请一支由两人组成的队伍参加奥林匹克竞赛。举行了组队预选赛,n名伯兰德学生参加了比赛。 Berland m 个地区每个地区至少有两名男生参加。资格赛每位参赛者的成绩为0至800之间的整数分。

每个赛区的队伍由该赛区预选赛的两名队员组成,不得由同赛区未入队且积分较高的男生代替。可能存在一种情况,某个地区的球队不能唯一组成,即满足上述属性的学校球队有多个。在这种情况下,该地区需要进行额外的比赛。如果该地区的两支球队中至少有一名男生属于一支球队而没有属于另一支球队,则认为该地区的两支球队是不同的。保证每个赛区至少有两名代表参加资格赛。

你的任务是,根据预选赛的结果,确定每个赛区的队伍,或者宣布该赛区的队伍需要进行额外的比赛。

输入

输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 10 000, n ≥ 2m)——资格赛的参赛人数和 Berland 的地区数量。

接下来的n行是资格赛参赛者的描述,格式如下:姓氏(长度为1到10个字符的大小英文字母组成的字符串)、地区编号(1到m的整数)和参赛者的得分(0到800的整数,含)。

保证所有参与者的姓氏均不相同,并且m个区域中每个区域至少有两人参与。仅字母大小写不同的姓氏应被视为不同。

输出

打印 m 行。在第 i 行打印第 i 个区域的团队 - 任意顺序的两个团队成员的姓氏,或单个字符“?” (不含报价)如果您需要在该地区进行进一步的资格赛。

示例

输入 #1

5 2
Ivanov 1 763
Andreev 2 800
Petrov 1 595
Sidorov 1 790
Semenov 2 503

输出 #1

Sidorov Ivanov
Andreev Semenov

输入 #2

5 2
Ivanov 1 800
Andreev 2 763
Petrov 1 800
Sidorov 1 800
Semenov 2 503

输出 #2

?
Andreev Semenov

注意

在第一个样本区域中,球队是唯一确定的。

在第二个样本中,区域 2 的队伍是唯一确定的,而区域 1 的队伍可以有三个队伍:“Petrov”-“Sidorov”、“Ivanov”-“Sidorov”、“Ivanov”-“Petrov”,因此不可能唯一确定一个队伍。