#6994. 护吾者,显其名

护吾者,显其名

题目背景(可以跳过)

众所周知,夏目贵志是世界上最温柔的人。(我老公

他遗传了外婆夏目玲子的强大妖力,从小就能看见各种各样的妖怪,他常常为此而苦恼并被周围人视为异类。直到他翻出了玲子的遗物——夏目友人帐,并结识了猫咪老师(娘口三三)——斑,他开始与妖怪正式打交道。夏目持有友人帐的事情在妖界传开了。每天都会有各种妖怪前来拜访夏目,或是请求他归还名字,或是想要夺取友人帐来控制其他妖怪(但是有三三在怎么可能得逞^-^)。

夏目归还名字需要在脑中想象那个妖怪的模样,“护吾者,显其名”,然后友人帐会自动显示出妖怪的名字,并且夏目能读取该妖怪与玲子之间的一段回忆。夏目每归还一个名字,都会消耗巨大的精力。

(夏目友人帐第七季上映了...(绝对没有在打广告

题目描述

这天,夏目和朋友出来玩,这里的妖怪听闻夏目大人在这里,纷纷赶来请求夏目归还名字。但是,夏目出来玩,精力很有限。为了让夏目在节省精力的情况下尽可能节省时间,三三召集了前来的妖怪们,让他们自己想个万全之策。

可以知道的是——

1.每只妖怪消耗的精力=自身能力值与前一个拜访者之间能力值的差值(第一个来拜访的妖怪消耗精力为其自身能力值)

2.名字越长,找寻时间越长。如果前一个妖的名字更长,那么找寻当前这个妖名字消耗的时间就可以缩短。

3.同等条件下,紧急程度高者优先,其余默认按照出现顺序。

(当然需要注意的是,妖怪中也不乏图谋不轨者。能力值中包含了7或者本身就是7的倍数的,就是前来夺友人帐的,三三会直接先把它们赶走。)

现在有n只妖怪前来拜访夏目,他们应该怎么做才能最好的满足三三的要求呢?

输入格式

第一行输入一个nn

接下来n行,每行分别输入一个妖怪的名字ss、能力值aa和紧急程度bb(紧急程度用大写字母A~Z表示,A表示最紧急)。

输出格式

请输出妖怪们的最佳拜访顺序。每行一个名字。(确保输出一定1≥1个)

测试样例

5
Sandu 200 F
Sanxiao 90000 Z
Lushen 200 A
Zhuo  170 D
Hetong 5000 Z
Lushen
Sandu
Hetong
Sanxiao

样例解释:

有五个妖怪,可知zhuozhuo的能力值包含了77,图谋不轨所以被赶走了。剩下的妖怪按照规则自觉排队。

数据范围:

30%30\%的数据1n1031≤n≤10^3

60%60\%的数据1n1041≤n≤10^4

100%100\%的数据1n5×1051≤n≤5\times10^5 , 名字ss的长度20≤20 , 0a1060≤a≤10^6