给你n个人的信息 n在 [1,30000] 每条有三个参数 ID号[不大于1000000]的整数 工资[不大于10000000的整数] 体重[1000000,2500000] 任何两个人的工资一定不同 体重有可能一样 给他们定一个领导关系 如果A是B的领导 那么A的体重一定不比B轻 并且A的工资也不低于B 假如 存在上两个条件的 A B 那么A可以是B的领导 最穷领导的定义 : 如果A 是B 的最穷领导 那么在B的领导中找不出一个人的工资比A低。。。 问: 给一个ID号 问他最多可以是多少人的领导 和 他的最穷领导 如果是老板(及没有人可以领导他 输出0);

Input

第一行 测试 数据组数。。 下面 第一行1 < = n < =30000 和下面询问次数 K (1,10000) 第 3 行开始每行三个数 。。。

Output

每组测试数据输出 K行 他的最穷的领导的ID 他最多可以是多少人的领导

Sample Input

2
3 3
123456 14323 1700000
123458 41412 1900000
123457 15221 1800000
123456
123458
123457
4 4
200002 12234 1832001
200003 15002 1745201
200004 18745 1883410
200001 24834 1921313
200004
200002
200003
200001

Sample Output

123457 0
0 2
123458 1
200001 2
200004 0
200004 0
0 3

Source

wqb0039