题目描述

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

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

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

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

样例

输入样例

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

输出样例

3
1
-1