题目描述

奶牛 Petr 有了一个新手机，她非常享受发短信的过程，但她的蹄子很大，在如此小的屏幕上输入非常麻烦，所以她一直会拼写错误。强哥 同意帮她开发一个自动补全应用，当输入单词的片段时，可以提示出完整的单词。

自动补全应用有权限访问一个包含 $W$ 个单词的字典，每个单词由范围在 $a \dots z$ 的小写字母组成，所有单词的字母总数不超过 $10^6$ 。用 $N$ （ $1 ≤ N ≤ 1000$ ）个单词片段的列表作为这个应用的输入，每个片段最多包含 $1000$ 个小写字母。对于每个片段 $i$ ，还需要提供一个整数 $K_i$ ，表示应用需要找到以片段 $i$ 作为前缀的所有单词中按照字典序排列的第 $K_i$ 个单词。也就是说，如果将所有的对片段 $i$ 合法补全后的单词进行排序，应用程序应该输出这个序列中的第 $K_i$ 个单词。

输入格式

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

第 $2 \dots W + 1$ 行：第 $i + 1$ 行包含字典中的第 $i$ 个单词。

第 $W + 2 \dots W + N + 1$ 行：第 $W + i + 1$ 行包含一个整数 $K_i$ 和一个单词片段。

输出格式

第 $1 \dots N$ 行：第 $i$ 行应该包含字典的一个下标（范围在 $[1, W]$ 的整数），表示第 $i$ 个片段的第 $K_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

提示

样例解释

以 a 为前缀的单词有 aa 、 aaa 、 aab 、 ab 、 abc 、 ac ，第 $4$ 个是 ab ，在字典的第 $3$ 行。以 da 为前缀的单词有 daa 、 dab 、 dadba ，第 $2$ 个是 dab ，在字典的第 $1$ 行。没有 $4$ 个单词以 da 为前缀。