USACO2014FEB，铜组第二题

题目描述

贝茜（Bessie）这头牛有了新手机，喜欢发短信，不过因为要用大蹄子在小屏幕上打字，总是出现拼写错误。农夫约翰答应帮她做一个自动补全应用，该应用接收一个部分单词（partial word），并给出补全建议。

这个自动补全应用可以访问一个包含 ( W ) 个单词的字典，每个单词由小写字母（a - z）组成，所有单词的总字母数不超过 ( 100,000 )。应用会接收 ( N ) 次查询，每次查询包含一个部分单词 ( i ) 和一个整数 ( K_i )。对于每个查询，应用需要找到按字典序排序后，以该部分单词为前缀的所有有效补全单词序列中，排在第 ( K_i ) 位的单词在字典中的原始索引（字典索引从 ( 1 ) 开始）；如果符合条件的补全单词不足 ( K_i ) 个，输出 ( -1 )。

输入格式

• 第 1 行：两个整数 ( W ) 和 ( N )，分别表示字典单词数量和查询次数。
• 第 2 至 ( W + 1 ) 行：第 ( i + 1 ) 行是字典中的第 ( i ) 个单词。
• 第 ( W + 2 ) 至 ( W + N + 1 ) 行：每行包含一个整数 ( K_i ) 和一个部分单词，描述一次查询。

样例输入

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

输出格式

对于每个查询，输出 1 行：

• 第 ( i ) 行输出字典中按字典序排列后，以第 ( i ) 个部分单词为前缀的补全单词里，第 ( K_i ) 位对应的字典原始索引（范围 ( 1 ... W ) ）；若不足 ( K_i ) 个，输出 ( -1 )。

样例输出

3
1
-1

输出详情

• 对于查询 4 a：
  以 a 为前缀的单词按字典序排序后是 aa, aaa, aab, ab, abc, ac，第 4 个是 ab，它在字典中是第 3 行（原始索引为 3 ）。
• 对于查询 2 da：
  以 da 为前缀的单词按字典序排序后是 daa, dab, dabba，第 2 个是 dab，它在字典中是第 1 行（原始索引为 1 ）。
• 对于查询 4 da：
  以 da 为前缀的单词只有 3 个，不足 4 个，输出 -1。