比赛的时候我是用后缀数组的，但是T了。
    赛后看了解题报告说，后缀数组貌似是卡你常数的时间，我算了下复杂度O（T * Q * n）。这是10 ^ 8,但是考虑到每次询问的时候都要重新构造字符，所以那个n可能是（3 - 4 ） * n,卡的可能就是这个常数。然后就过不了了。
    我先上一发我的后缀数组的代码，T的好惨。
    因为当时不会后缀自动机。
    #include<iostream>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include <cstdio>
    using namespace std;
    const int N=2005;
    /****后缀数组模版****/
    #define F（x）（（x）/3+（（x）%3==1 0:tb）） //F（x）求出原字符串的suffix（x）在新的字符串中的起始位置
    #define G（x）（（x）<tb （x）*3+1:（（x）-tb）*3+2） //G（x）是计算新字符串的suffix（x）在原字符串中的位置，和F（x）为互逆运算
    int wa[N],wb[N],wv[N],WS[N];
    int sa[N*3] ;
    int rank1[N],height[N];
    int r[N*3];
    int c0（int *r,int a,int b） {
    return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];
    }
    int c12（int k,int *r,int a,int b） {
    if（k==2）
    return r[a]<r[b] || （ r[a]==r[b] && c12（1,r,a+1,b+1） ）；
    else
    return r[a]<r[b] || （ r[a]==r[b] && wv[a+1]<wv[b+1] ）；
    }
    void sort（int *r,int *a,int *b,int n,int m） {
    int i;
    for（i=0; i<n; i++）
    wv[i]=r[a[i]];
    for（i=0; i<m; i++）
    WS[i]=0;
    for（i=0; i<n; i++）
    WS[wv[i]]++;
    for（i=1; i<m; i++）
    WS[i]+=WS[i-1];
    for（i=n-1; i>=0; i--）
    b[--WS[wv[i]]]=a[i];
    return;
    }
    //注意点：为了方便下面的递归处理，r数组和sa数组的大小都要是3*n
    void dc3（int *r,int *sa,int n,int m） { //rn数组保存的是递归处理的新字符串，san数组是新字符串的sa
    int i , j , *rn = r+n , *san = sa+n , ta = 0 ,tb = （n+1）/3 , tbc = 0 , p;
    r[n] = r[n+1] = 0;
    for（i=0; i<n; i++） {
    if（i%3!=0）
    wa[tbc++]=i; //tbc表示起始位置模3为1或2的后缀个数
    }
    sort（r+2,wa,wb,tbc,m）；
    sort（r+1,wb,wa,tbc,m）；
    sort（r,wa,wb,tbc,m）；
    for（p=1,rn[F（wb[0]）]=0,i=1; i<tbc; i++）
    rn[F（wb[i]）]=c0（r,wb[i-1],wb[i]）？p-1:p++;
    if（p<tbc）
    dc3（rn,san,tbc,p）；
    else {
    for（i=0; i<tbc; i++）
    san[rn[i]]=i;
    }
    //对所有起始位置模3等于0的后缀排序
    for（i=0; i<tbc; i++） {
    if（san[i]<tb）
    wb[ta++]=san[i]*3;
    }
    if（n%3==1）  //n%3==1,要特殊处理suffix（n-1）
    wb[ta++]=n-1;
    sort（r,wb,wa,ta,m）；
    for（i=0; i<tbc; i++）
    wv[wb[i]=G（san[i]）]=i;
    //合并所有后缀的排序结果，保存在sa数组中
    for（i=0,j=0,p=0; i<ta&&j<tbc; p++）
    sa[p]=c12（wb[j]%3,r,wa[i],wb[j]）？wa[i++]:wb[j++];
    for（； i<ta; p++）
    sa[p]=wa[i++];
    for（； j<tbc; p++）
    sa[p]=wb[j++];
    return;
    }