题目描述

奶牛贝西有了一部新手机，她很喜欢发短信，尽管她经常犯拼写错误，因为她的大蹄子在这么小的屏幕上打字有困难。

农场主约翰同意帮她写一个自动补全的应用程序，它会提取一个单词的一部分，并给出补全建议。

动完成应用程序可以访问包含$\red{W}$个单词的字典，每个单词由小写字母组成，范围为$\red{a..Z，}$其中所有单词中的字母总数最 多不超过$\red{1,000,000}$个。

应用程序给出了一个由$\red{N}$个部分单词$\red{(1 <= N <= 1000)}$组成的列表，每个单词最多包含$\red{1000}$个小写字母。除了每个部分单词$\red{i}$之外，还提供了一个整数$\red{K_i，}$这样应用程序必须找到以部分单词$\red{i}$作为前缀的$\red{(K_i)}$第一个字母顺序的单词。

也就是说，如果对第$\red{i}$个部分单词的所有有效补全排序，应用程序应该输 出补全结果

贝西新买了手机，打字不方便，请设计一款应用，帮助她快速发消息。

字典里有$\red{W（}$$\red{W<=30000）}$个小写字母构成的单词，所有单词的字符总数量不超过$\red{1,000,000，}$这些单词是无序的。

现在给出$\red{N(1 <= N <= 1000)}$个询问，每个询问$\red{i}$包含一个的字符串$\red{s_i（}$每个字符串最多包含$\red{1000}$ 个字符）和一个整数$\red{K_i，}$对于所有以$\red{s_i}$为前缀的单词，其中按字典序排序后的第$\red{K_i}$个单词，

求该单词在原 字典里的序号

输入格式

第一行:两个整数:$\red{W}$和$\red{N}$。

第$\red{2 . .W+1}$行:第$\red{i}$行$\red{+1:}$字典中的第$\red{i}$个单词。

第$\red{W + 2 . .W+N+1}$行:第$\red{W+i+1}$行:单个整数$\red{K_i}$后跟一个部分单词。

输出格式

第$\red{1 . .N}$行:第$\red{i}$行应该包含字典中的索引 $\red{(K_i)}$第$\red{(K_i)}$次补全$\red{( \in}$第$\red{i}$个部分单词的字母顺序$\red{)}$，

如果有，则为$\red{-1}$尽次数小于$\red{K_i}$。

样例

输入样例

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

输出样例

3
1
-1