题目描述

Reuben在沼泽迷路了，此时“善良“的女巫出现了她有一个史莱姆农场，她说可以帮助它离开沼泽，前提是帮她一个忙：对清单中的物品进行排序，以便优先选择。

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


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


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


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


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


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


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


(easy版为hard版的削弱版，两者不同的是easy的q固定为 2 ，同时 a 和 b  的值较小，保证不爆Long)

输入格式

第一行包含一个整数 T

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


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


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


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


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

输出格式

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

1
2 2
apple 5 3
Reuben 10 0

apple Reuben

提示