描述

多项调查表明，你越高，在公司的晋升空间就越大。在“高大”企业公司，这个“事实上的标准”已经被恰当地正式化了：你的老板总是至少和你一样高。此外，你可以放心地认为你的老板挣得比你多一点。实际上，你可以绝对肯定你的直属老板是所有挣得比你多且至少和你一样高的员工中挣得最少的那个人。而且，如果你是某个人的直属老板，那个人就是你的下属，并且他的所有下属也都是你的下属。如果你没有下属，那么你就没有下属。尽管这些规则很简单，但在“高大”企业工作的许多人不确定他们应该向谁提交每周进度报告，以及他们有多少下属。编写一个程序，帮助确定对于任何员工，其直属老板是谁以及他们有多少下属。“高大”企业的质量保证部门设计了一系列测试，以确保你的程序是正确的。这些测试描述如下。

输入

输入的第一行是一个正整数n，表示接下来测试场景的数量。每个场景的第一行包含两个正整数m和q，其中m（最多30000）是员工的数量，q（最多200）是查询的数量。接下来的m行，每行用三个整数列出一名员工：员工身份证号码（六位十进制数字，第一位不为零）、年薪（欧元）以及身高（微米，1微米 = (10^{-6})米——在“高大”企业，精度很重要）。公司的董事长是挣得比其他任何人都多且也是公司里最高的员工。然后有q行列出查询内容。每个查询是一个合法的员工身份证号码。

年薪是一个正整数，最多为10000000。没有两个员工有相同的身份证号码，也没有两个员工有相同的年薪。员工的身高至少为1000000微米，最多为2500000微米。

输出

对于每个查询中的员工身份证号码x，输出一行，包含两个整数y和k，用一个空格分隔，其中y是x的老板的身份证号码，如果x是董事长，由于董事长没有直属老板（可能除了上帝），则y为0；k是x的下属数量。

输入数据 1

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

输出数据 1

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

来源

2003年西北欧竞赛