题目描述

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

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

字典包含 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 }第 2个是 vp，其在输入中为第 3 个，故输出为 3。同理，对于第 2 个和第 3 个询问是在字典中找到以 ick 为前缀且按字典序排序后的第 1 个字符串。而以 ick 为前缀的字符串按字典序排序后第 1 个为icktcyb，其在输入中为第 7 个，故第 2 个输出为 7。

数据范围

对于 20% 的数据，有 w<=200,n<=100,每个单词长度不超过 100。

对于 60% 的数据，有 w<=5000,n<=200,每个单词长度不超过 200。

对于 100% 的数据，有 w<=30000,n<=1000,每个单词长度不超过 1000