struct ACM{

    int ch[N][],f[N],cnt[N];

    int sz,rt;

    int ins(char *s){

        int n=strlen(s),u=rt;

        for(int i=;i<n;i++){

            int c=s[i]-'a';S[tot++]=s[i];

            if(!ch[u][c])ch[u][c]=++sz;

            u=ch[u][c];

        }

        cnt[u]=;

        return u;

    }

    void build(){

        queue<int>q;

        while(!q.empty())q.pop();

        int u=;

        for(int c=;c<;c++){

            int *v=&ch[rt][c];

            if(*v)

            f[*v]=rt,q.push(*v);

            else *v=rt;

        }

        while(!q.empty()){

            int u=q.front();q.pop();

            for(int c=;c<;c++){

                int *v=&ch[u][c];

                if(*v){

                    f[*v]=ch[f[u]][c];q.push(*v);

                }

                else *v=ch[f[u]][c];

            }

        }

    }

    void query(char *s){

        int n=strlen(s),u=rt;

        for(int i=;i<n;i++){

            if(s[i]=='#'){

                u=;continue;

            }

            int c=s[i]-'a';

            while(u&&!ch[u][c])u=f[u];

            u=ch[u][c];

            int v=u;

            while(v){

                if(cnt[v])cnt[v]++;

                v=f[v];

            }

        }

    }

}Aho;