背景

    想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小的数

 1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define inf (1<<30)14 #define N (500010)15 #define il inline16 #define RG register17 #define ll long long18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)19 20 using namespace std;21 22 int ch[N][26],sum[20*N],ls[20*N],rs[20*N],rt[N],len[N],n,sz,cnt;23 string s[N];24 25 il int gi(){26     RG int x=0,q=1; RG char ch=getchar();27     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();28     if (ch==‘-‘) q=-1,ch=getchar();29     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();30     return q*x;31 }32 33 il void update(RG int &x,RG int l,RG int r,RG int p){34     if (!x) x=++cnt; ++sum[x]; if (l==r) return; RG int mid=(l+r)>>1;35     p<=mid?update(ls[x],l,mid,p):update(rs[x],mid+1,r,p); return;36 }37 38 il int query(RG int x,RG int l,RG int r,RG int k){39     if (l==r) return l; RG int mid=(l+r)>>1,tmp=sum[ls[x]];40     return k<=tmp?query(ls[x],l,mid,k):query(rs[x],mid+1,r,k-tmp);41 }42 43 il void insert(string s,RG int len,RG int p){44     RG int x=0,c;45     for (RG int i=len-1;i>=0;--i){46     c=s[i]-97; if (!ch[x][c]) ch[x][c]=++sz;47     x=ch[x][c],update(rt[x],1,n,p);48     }49     return;50 }51 52 il int find(string s,RG int len,RG int k){53     RG int x=0,c;54     for (RG int i=len-1;i>=0;--i) c=s[i]-97,x=ch[x][c];55     return sum[rt[x]]>=k?query(rt[x],1,n,k):-1;56 }57 58 il void work(){59     n=gi();60     for (RG int i=1;i<=n;++i)61     cin>>s[i],len[i]=s[i].length(),insert(s[i],len[i],i);62     for (RG int i=1,k;i<=n;++i)63     k=gi(),printf("%d\n",find(s[i],len[i],k));64     return;65 }66 67 int main(){68     File("kpm");69     work();70     return 0;71 }