题目描述

奶牛贝茜买了一个新手机，并十分喜欢用它发短信。

但是它的大蹄子在手机的小屏幕上打字时遇到了麻烦，它总是把单词拼错。

农夫约翰同意通过编写一个自动补全程序来帮助它，当它输入部分单词时，该应用程序可以给出补全建议。

自动补全程序可以访问一个包含 W 个单词的词典，每个单词由 a…z 范围内的小写字母组成，其中所有单词中的字母总数最多为 1000000。

现在给定一个包含 N 个部分单词的列表，每个部分单词最多包含 1000 个字母。

对于每个部分单词 i，还会提供一个整数 Ki，自动补全程序需要找到词典中以部分单词 i 作为前缀的所有单词中，按字典序排序排在第 Ki 个的单词。

也就是说，对所有部分单词 i 的有效补全按字典序进行排序，输出此顺序下的第 Ki 个补全。

输入格式

第一行包含两个整数 W 和 N。

接下来 W 行，按单词在词典中的顺序，每行描述一个单词。字典中的所有字符串均互不相同。

接下来 N 行，每行首先包含一个整数 Ki，然后包含一个部分单词 i。

输出格式

共 N 行，第 i 行输出部分单词 i 的第 Ki 个有效补全在词典中出现的位置（一个 1∼W 之间的整数）。

如果第 Ki 个有效补全不存在，则输出 −1。

数据范围

1≤W≤30000, 1≤N≤10000 1≤Ki≤W

样例

输入样例：

10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da

输出样例：

3
1
-1
1
2
3

样例解释

a 的自动补全为 aa,aaa,aab,ab,abc,ac，第四个为 ab，在词典中排第 3 个。

da 的自动补全为 daa,dab,dadba，第二个为 dab，在词典中排第 1 个。

da 不存在第四个自动补全。