自动补全 APP

题目描述

奶牛 Bessie 得到了一部新手机。尽管她的前蹄过于庞大，难以在小小的屏幕上打字，导致她不断地拼写错误，她仍旧很喜欢发短信。

农夫 John 许诺帮她写一个输入单词的一部分、然后推荐补全方案的自动补全 APP。这个自动补全 APP 会查阅有 W 个单词的词典，其中每个单词由小写字母 a～z 组成。

一个包含 N个单词前缀以及对应的整数 $K_i$ 的列表将作为 APP 的输入。这个 APP 需要在词典中找到以该前缀开头的所有单词里，按字母表顺序排列的第 $K_i$ 个单词。也就是说，如果列出第 i 个单词前缀的所有可能补全方案，这个 APP 应该输出这个序列中的第 $K_i$ 个补全方案在原词典中的序号。

输入描述

第 1 行：两个整数 W 和 N。

第 2～W+1 行：其中第 i+1 行为词典中的第 i 个单词。

第 W+2～W+N+1 行：其中第 W+i+1 行为整数 $K_i$ 以及一个单词前缀。

输出描述

第 1～N 行：第 i 行应该包含第 i 个单词前缀的第 $K_i$ 个补全方案（也就是词典中的单词）在词典中的序号。如果补全方案少于 $K_i$ 个，则输出 -1。

样例

输入：

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

输出：

3
1
-1

样例解释：前缀 a 的补全方案有 {aa, aaa, aab, ab, abc, ac}。第 4 个是 ab，它在词典的第 3 行。前缀 da 的补全方案有 {daa, dab, dadba}。第 2 个是 dab，在词典的第 1 行。前缀 da 没有第 4 个补全方案。

输入样例 #2

1 3
a
1 a
2 a
1 b

输出样例 #2

1
-1
-1

输入样例 #3

4 4
ab
a
aa
b
1 a
3 a
4 a
1 b

输出样例 #3

2
1
-1
4

数据范围

所给单词的个数不超过 1,000,000。

1 ≤ N ≤ 1000