#3439. Kpm的MC密码

题目描述

背景

想Kpm当年为了防止别人随便进入他的MC，给他的PC设了各种奇怪的密码和验证问题（不要问我他是怎么设的。。。），于是乎，他现在理所当然地忘记了密码，只能来解答那些神奇的身份验证问题了。。。

描述

Kpm当年设下的问题是这样的：

现在定义这么一个概念，如果字符串s是字符串c的一个后缀，那么我们称c是s的一个kpm串。

系统将随机生成n个由a…z组成的字符串，由1…n编号（s1,s2…,sn），然后将它们按序告诉你，接下来会给你n个数字，分别为k1…kn，对于每一个ki，要求你求出列出的n个字符串中所有是si的kpm串的字符串的编号中第ki小的数，如果不存在第ki小的数，则用-1代替。（比如说给出的字符串是cd,abcd,bcd,此时k1=2，那么"cd"的kpm串有"cd","abcd","bcd",编号分别为1,2,3其中第2小的编号就是2）（PS：如果你能在相当快的时间里回答完所有n个ki的查询，那么你就可以成功帮kpm进入MC啦~~）

输入格式

第一行一个整数 n 表示字符串的数目

接下来第二行到n+1行总共n行，每行包括一个字符串，第i+1行的字符串表示编号为i的字符串

接下来包括n行，每行包括一个整数ki，意义如上题所示

输出格式

包括n行，第i行包括一个整数，表示所有是si的kpm串的字符串的编号中第ki小的数

样例

样例输入

    3  

    cd  

    abcd  

    bcd  

    2  

    3  

    1  

样例输出

    2  

    -1  

    2  

  

样例解释  

  

    “cd”的kpm 串有”cd”,”abcd”,”bcd”,编号为1,2,3，第2小的编号是  

  

    2，”abcd”的kpm串只有一个，所以第3小的编号不存在，”bcd”的kpm  

  

    串有”abcd”,”bcd”,第1小的编号就是2。  

  

数据范围与约定  

  

    设所有字符串的总长度为len  

  

  

    对于100%的数据，1<=n<=100000,0

数据范围与提示