说明

本题需要使用文件重定向，输入文件名dictionary.in，输出文件名dictionary.out

题目描述

神秘的海底九万里处有一个鱼人国度，鱼人们非常聪明，会制作武器捕猎，也会利用海草和小海星圈养自己的食物（各种各样的鱼）。但是鱼人们有一个最大的缺陷：语言不通！因此鱼人国度的国王决定要兴起一波学英文的潮流，用英文来替代“咿咿呀呀”的嚎叫。

但是对于鱼人们来说，英文实在太难了。你作为鱼人国英文最好的鱼，被国王任命制作一本字典，来帮助鱼人国的国民们进行英文的查询及学习。

字典包含 $w$个由小写字母构成的单词（鱼人没有大写字母），每个查询字典的鱼人会给出一个由字符串 $s$ 和正数 $k$ 构成的询问，需要字典自动弹出在 $w$个单词里，字典序排序第$k$ 位，且前缀为 $s$的单词在字典中的位置。若不存在，则输出-1。

输入格式

第 1 行为两个正整数 $w，n$。分别表示单词的数量和鱼人询问的次数。

第 2 行到第$w$+1 行，每行输入一个字符串，表示字典中的一个单词。

最后$n$行，每行输入一个整数$k$ 和一个字符串 $s$，表示鱼人的一次询问。

输出格式

输出$n$行，每行一个整数，表示查询结果。

样例

12 3
ickteg
ickthse
vp
ymtpxgau
ymtpxc
vqox
icktcyb
vi
ymtpxu
icktei
ickteg
ymtpxwe
2 v
1 ick
4 ym

3
7
12

样例解释

• 对于第 1 个询问，含义为在字典中找到以 v 为前缀且按字典序排序后第 2 个字符串，而字典中以 v 为前缀且按字典序排序后字符串为{vi,vp,vqox }，第 2 个字符串是 vp，其在输入中序号为第 3 个，故第一个询问输出为 3。
• 对于第 2 个询问是在字典中找到以 ick 为前缀且按字典序排序后的第 1 个字符串。而以 ick 为前缀的字符串按字典序排序后为{icktcyb,ickteg,ickteg,icktei,ickthse}，第 1 个字符串为 icktcyb，其在输入中序号为第 7 个，故第 2 个询问输出为 7。
• 对于第 3个询问是在字典中找到以 ym 为前缀且按字典序排序后的第 4 个字符串。而以 ym 为前缀的字符串按字典序排序后为{ymtpxc,ymtpxgau,ymtpxu,ymtpxwe}，第 4 个字符串为 ymtpxwe，其在输入中序号为第 12 个，故第 3 个询问输出为 12。

数据范围

• 对于 20% 的数据，有 $w \le 200,n \le 100$,每个单词长度不超过 100。
• 对于 60% 的数据，有 $w \le 5000,n \le 200$,每个单词长度不超过 200。
• 对于 100% 的数据，有 $w \le 30000,n \le 3000，k \le 30000$,每个单词长度不超过 1000。

来源

BCSP-X 2024 初中组 T3