字符串联想是一个被广泛用于搜索引擎输入法的功能。联想算法根据一定规则，计算出与待匹配字符串最接近的若干个联想结果。聪明的ttt觉得这功能很好，希望刚入职的lhy也实现一个简单的联想算法。 ttt：客户端将提供一个最优匹配结果数k，一个待匹配字符串，和若干个命令。希望你能实现一个算法，它实现两种操作： A: 增加一项搜索记录 P: 打印当前的k个最优匹配结果 我们规定每个匹配记录（record）需满足：record中存在至少一个与s完全匹配的子串。 并规定，若满足下列条件，则称record a是比record b更好的匹配记录 1.record a长度短于record b 2.长度相同，record a的字典序小于record b 这可把热爱摸鱼的lhy难倒了。为了帮lhy保住工作，和ttt一样聪明的你能帮帮lhy吗？

输入描述:

输入数据包含n + 3行每一组数据由三行组成第一行：n第二行：k第三行：s第四行~n+3行：[A record] 或 [P]n: 需执行的总命令数 (n 输入数据保证每条字符串长度 (0

输出描述:

每次P命令执行后，输出P:k行数据（不允许有重复数据，相同的看做同一条数据）。不足k行则输出所有符合题干条件的记录。输出顺序需按提干条件由优先级高-低顺序排列

备注:

保证所有查询的输出结果加在一起字符总长度不超过5×106