100000042 - 字典树

Time Limit

1000 毫秒

Memory Limit

512 MB

通过次数

9

提交次数

35

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

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

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

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

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

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

Input

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

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

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

对于100%的数据:

10^5\le n \le 10^7

1 \le x \le 5

Output

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

Examples

Input

6
1 HaiMian BaoBao
1 Zhang YuGe
2 Zhan 3
1 Zhang San
1 Zhang SanFeng
2 Zhang 2

Output

0
3
San
SanFeng