Time Limit: 1000 MS    Memory Limit: 131072 K 


Description

当鸣人当上了七代火影的时候,mathon真心地替鸣人高兴,他想起了三代火影爷爷,想起了自来也,想起了宁次.....他们都为了保护这个村子付出了生命,自己的梦想也是要成为火影, 用自己的生命去保护这个有爱的村子. 但是隔壁的宇智波-liujc也想要成为火影.介于宇智波一族天生的写轮眼,mathon必须学会比他更多的忍术才行. 为了当上八代目火影,mathon有一大堆忍术需要修炼:有简单如鸣人的色诱之术,只需要很少的时间就能学会.也有困难如四代火影的螺旋丸,需要很长时间... 现在有n个忍术需要你去学习,每个忍术的学习时间是t.你需要决定这n个忍术的学习顺序. 从现在这个时刻开始,记为0时刻,每个忍术在学习它之前所经历的时间为该忍术 的等待时间(第一个忍术的等待时间为0),你的任务是合理的安排这些忍术的学习顺序让所有忍术的等待时间的平均值最小. 然而mathon发现有一对不同的忍术是有依赖关系的, 一个忍术必须要在学会了另一个忍术之后才能学习,所以你在安排顺序的时候必须满足这对忍术的依赖关系.

Input

第一行一个数字T,表示有T组数据. 每组数据描述如下: 一个数n(n <= 10^5),代表有n个忍术需要学习. 下面n + 1行,前n行每行有一个字符串(只包含小写字母且长度小于11),和一个数字t (0 < t < 10^14),分别表示这个忍术的名字和它的学习时间 (注意这里保证每一个忍术的学习时间不一样). 最后一行,每行两个字符串a和b,表示忍术a必须在忍术b之前学习.

Output

对于每组数据 按学习顺序输出n行,每行一个字符串,表示忍术的名字.

Sample Input

1 3 luoxuanwan 100 seyouzhishu 1 dibaotianxing 1000 luoxuanwan seyouzhishu

Sample Output

luoxuanwan seyouzhishu dibaotianxing