JZPGYZ  Sevenk Love Oimaster
Oimaster and sevenk love each other.
But recently,sevenk heard that a girl named ChuYuXun was dating with oimaster.As a woman's nature, sevenk felt angry and began to check oimaster's online talk with ChuYuXun. Oimaster talked with ChuYuXun 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?"
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. Example
Input:3 3hi,I'mChuYuXun..YouaresohandsomethatIfallinlovewithyoubutIlovesevenk..you'dbettergoaway55555555555ChuYuXunyou55555555
Output:121
hide comments
Raihat Zaman Neloy:
20160613 12:06:58
10^5 * 600 also passes the TL :) Nice problem to solve :) 

Ankita Victor:
20150621 06:54:19
how is the answer to the last test case 1? 

Jacob Plachta:
20140213 14:43:10
Some of the constraints regarding sums of string lengths aren't met. 

Sotirios Nikoloutsopoulos:
20120618 14:09:37
@Tom Chen , can you tell me why my submission with ID : 7171738 gets WA?


Radhakrishnan Venkataramani:
20110601 00:26:07
Can u tell whats the size of input File ? 

张钧瑞:
20110417 03:23:00
The task is so difficult for me to solve~ 

mike_nzk:
20101220 02:12:47
The question is "how many strings",so you should output the number of strings, not the number of substrings. 

Garg Ankit:
20101219 22:15:04
the last test case in the example above should yield the answer 4(according to me). Can anyone explain how is it 1? 

Robert Gerbicz:
20101219 22:03:18
After about ~20 sigabrt I've discovered that assert(0<=n&&0<=q); gets also runtime error, what is a big mistake.


mike_nzk:
20101219 06:29:08
I used an O(total_length_of_question_strings*log(total_length_of_n_strings)) algorithm and got AC. The time limit is not strict at all :) Last edit: 20101219 06:30:30 
Added by:  Tom Chen 
Date:  20101218 
Time limit:  0.100s0.161s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem 