100000043 - 字典树的子树

小明向一个空的数据库中录入姓名数据，使得数据库能够提供常用的人名的拼音表示，其格式为每个汉字的拼音首字母大写其余小写，姓与名之间用一个空格分隔，例如Zhang San、Zhang SanFeng。

小亮需要提供一个查询系统，其功能是当用户输入一个姓之后，显示当前数据库中该姓的人名共有多少，并打印按字典序排序的前x个。

为了描述的更清楚，我们把小明的操作定义为OP1，把小亮的操作定义为OP2：

1 Zhang San表示向数据库内添加一个姓名为Zhang San的数据。小明是一个非常认真的人，不会在输入过程中发生任何错误。需要注意的是，如果该数据原来就存在则不会被重新添加。

2 Zhang x表示从数据库提取姓为Zhang的人名，并返回该姓的人的总数、以及按字典序排序的前x个。需要注意的是，有的姓是“复姓”即由多个字构成的姓，例如欧阳、司马等。

上次由于小亮刚刚学会字典树，所以他认为自己的水平还无法用字典树解决这么复杂的问题。于是你帮助小亮完成了查询工作。

众所周知，客户需求总是又发生了变化，他们认为仅仅是按照字典序输出是不合理的——应该按名字被输入的次数从多到少排序，而后次数相同的部分按字典序排序，这样才更符合要求。

于是，现在这个任务又一次被小亮交给你了。实际上你写的代码能力不比小亮高很多，但是你更善于分析问题使之一层一层的解决。所以，你现在的目标是假设已经按姓找到了一颗子树，每当向这颗子树添加一个名，就对其进行按客户需求排序并输出前x个。

第一行，两个整数n,x分别表示添加到该子树的名字个数和输出前几个。

接下来n行，每行一个首写字母大写其余小写的字符串name，表示名的拼音。

对于100%的数据：

10^4 \le n \le 10^5;

2 \le x \le 5;

2 \le |name| \le 6，即名的拼音长度不少于2不多于6。

对于每行输入输出前x个按客户需求排序的名的拼音。