Description

Oimaster and sevenk love each other.

But recently,sevenk heard that a girl named ChuYuXun was dating with oimaster.As a woman's nature, s

evenk felt angry and began to check oimaster's online talk with ChuYuXun.    Oimaster talked with Ch

uYuXun n times, and each online talk actually is a string.Sevenk asks q questions like this,    "how

 many strings in oimaster's online talk contain this string as their substrings?"

有n个大串和m个询问，每次给出一个字符串s询问在多少个大串中出现过

Input

There are two integers in the first line, 

the number of strings n and the number of questions q.

And n lines follow, each of them is a string describing oimaster's online talk. 

And q lines follow, each of them is a question.

n<=10000, q<=60000 

the total length of n strings<=100000, 

the total length of q question strings<=360000

Output

For each question, output the answer in one line.

Sample Input

3 3

abcabcabc

aaa

aafe

abc

a

ca

Sample Output

1

3

1

解题思路：

利用Parent树的子节点都是父节点母串的性质，在大串的每个实节点打上标记，然后构建出这颗Parent树。

那么我们的问题就变成了在一个Fail节点子树内不同颜色个数。

像不像HH的项链？

把Dfs序构建出来，离线树状数组就好了。

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 const int N=200000;  5 const int M=1000000;  6 struct sant{  7     int tranc[26];  8     int len;  9     int pre; 10 }s[N]; 11 struct pnt{ 12     int hd; 13     int col; 14     int ind; 15     int oud; 16 }p[N]; 17 struct ent{ 18     int twd; 19     int lst; 20 }e[N]; 21 struct qust{ 22     int l,r; 23     int ans; 24     int no; 25 }q[N]; 26 int siz; 27 int fin; 28 int n,Q; 29 int cnt; 30 int dfn; 31 char tmp[N]; 32 int line[N]; 33 int lst[N]; 34 int phr[N]; 35 int col[N]; 36 void Insert(int c,int whic) 37 { 38     int nwp,nwq,lsp,lsq; 39     nwp=++siz; 40     p[nwp].col=whic; 41     s[nwp].len=s[fin].len+1; 42     for(lsp=fin;lsp&&!s[lsp].tranc[c];lsp=s[lsp].pre) 43         s[lsp].tranc[c]=nwp; 44     if(!lsp) 45         s[nwp].pre=1; 46     else{ 47         lsq=s[lsp].tranc[c]; 48         if(s[lsq].len==s[lsp].len+1) 49             s[nwp].pre=lsq; 50         else{ 51             nwq=++siz; 52             s[nwq]=s[lsq]; 53             s[nwq].len=s[lsp].len+1; 54             s[nwp].pre=s[lsq].pre=nwq; 55             while(s[lsp].tranc[c]==lsq) 56             { 57                 s[lsp].tranc[c]=nwq; 58                 lsp=s[lsp].pre; 59             } 60         } 61     } 62     fin=nwp; 63     return ; 64 } 65 void ade(int f,int t) 66 { 67     cnt++; 68     e[cnt].twd=t; 69     e[cnt].lst=p[f].hd; 70     p[f].hd=cnt; 71     return ; 72 } 73 void Dfs(int x) 74 { 75     p[x].ind=++dfn; 76     phr[dfn]=x; 77     col[dfn]=p[x].col; 78     for(int i=p[x].hd;i;i=e[i].lst) 79     { 80         int to=e[i].twd; 81         Dfs(to); 82     } 83     p[x].oud=dfn; 84     return ; 85 } 86 bool cmp(qust x,qust y) 87 { 88     return x.r