题目描述

小珅和小泽都很喜欢体验新游戏。每当不知道该玩什么时，他们就会到游戏应用平台查看其他玩家留下的评分。

为了选出最值得下载的游戏，他们收集了若干条评分记录。每条记录包含一个游戏名和一名玩家给出的分数。同一个游戏可能有多条评分记录。

小珅和小泽约定，先比较游戏的平均分，平均分高的排在前面；如果平均分相同，评分人数多的排在前面；如果平均分和评分人数都相同，则游戏名的字典序较小者排在前面。

请你帮助他们找出排名最靠前的 K 个游戏。

输入格式

第一行包含两个整数 N 和 K，分别表示评分记录的数量，以及需要选出的游戏数量。

接下来 N 行，每行包含一个字符串和一个整数，分别表示游戏名和本次评分。两者之间用一个空格分隔。同一个游戏可以出现多次。

输出格式

输出 K 行，每行输出一个游戏名，按照题目规定的排名顺序排列。

5 1
yuanshen 9
xiangchangpaidui 8
yuanshen 8
yuanshen 7
guangyu 7

yuanshen

10 3
a 9
b 10
q 8
d 8
c 5
k 7
b 4
c 8
d 6
q 9

a
q
b

样例说明

在样例 1 中，yuanshen 和 xiangchangpaidui 的平均分都是 8 分，但 yuanshen 的评分人数更多，所以排名更靠前。

数据范围

• 对于 30% 的数据，1 < N <= 2000；
• 对于 100% 的数据，1 < N <= 200000；
• 游戏名只由小写英文字母和数字组成，长度不超过 50；
• 不同游戏的数量不少于 K；
• 每次评分均为 0 到 10 之间的整数。

2 1
onlygame 10
onlygame 0

onlygame