题目描述

Reuben在沼泽迷路了，现在它找到了一个史莱姆农场。

此时农场里一位"善良"的女巫出现了，她说可以帮助它离开沼泽，前但提是帮她一个忙：对清单中的物品进行排序，以便优先选择。


清单中有n种物品，每种物品有以下属性：


物品 id：一个字符串，用于标识这种物品


初始值 a：一个整数，表示这种物品可以让史莱姆变成多大的初始值


最大增值 b：一个整数，表示这种物品可以让史莱姆增大的最大次数


（史莱姆在吃第一次会变成这个物品的初始值，之后喂食相同物品每次可以固定让史莱姆增大q倍，但是有最大增值的限制增大次数）


Reuben需要根据每种物品最多可以让史莱姆变成多大的值进行排序


（降序输出，如果结果一样大，则根据id字典序排序）

输入格式

第一行包含一个整数 T

（1 ≤ T ≤ 25，表示测试用例的数量）


每个测试用例的第一行包含2个整数 n, q


（1 ≤ n ≤ 2000，2 ≤ q ≤ 16，分别表示物品种类和固定增大的倍数）


接下来n行每行包括物品id，初始值 a，最大增值 b 


（0≤ a, b ≤ 1e12，保证物品id无重复）

输出格式

输出排序结果，每个结果用一个空格隔开

1
2 2
apple 5 3
Reuben 10 0

apple Reuben

提示