100000042 - 字典树

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

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

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

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

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

由于小亮刚刚学会字典树，所以他认为自己的水平还无法用字典树解决这么复杂的问题。所以，小亮找到了你。

第一行，一个整数n，表示所有操作共有多少次。

接下来n行，格式为1 姓的拼音 名的拼音或2 姓的拼音 x，分别表示小明和小亮的操作。

输入保证汉字的拼音首字母大写其余小写，每个汉字的拼音所含字母数不超过合法的汉字拼音长度，每个人的姓不超过2个汉字，名不超过4个汉字。

对于100%的数据：

10^5\le n \le 10^7；

1 \le x \le 5。

对于每个OP2按要求进行输出，输出的值每行一个。如果实际存在的姓名拼音个数为0只需要输出0即可；如果个数不为0，但小于x，则按字典序输出所有符合条件的姓名；如果个数大于要求的个数，则按字典序输出前x个。