const int ChSize=;

struct PerTrie

{

    int next[maxn*][ChSize];

    int id,inf[maxn*];

    void init()

    {

        memset(next[],,sizeof(next[]));

        inf[]=;

        id=;

    }

    int GetId(char c){ return c-'a'; }

    void Insert(int& rt,int pre,char* S,int x) //插入

    {

        rt=++id;

        inf[rt]=inf[pre]+;

        for(int i=;i<ChSize;i++) next[rt][i]=next[pre][i]; //把前面的赋给当前

        if(S[x]=='\0') return;

        Insert(next[rt][GetId(S[x])],next[pre][GetId(S[x])],S,x+);

    }

    int Query(int le,int ri,char* S) //查询[le,ri]

    {

        for(int i=;S[i]!='\0';i++)

        {

            int s=GetId(S[i]);

            le=next[le][s];

            ri=next[ri][s];

        }

        return inf[ri]-inf[le];

    }

}PT;