题目描述

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 ≤ 10^{12}$，保证物品 $id$ 无重复）

输出格式

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

1
2 2
apple 5 3
Reuben 10 0

apple Reuben