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
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 

Siarhei Kulik:
20101218 20:41:52
Can O(total_length_of_question_strings*log(total_length_of_n_strings)) pass or should I search for a better algo? Last edit: 20101218 20:42:13 

[Trichromatic] XilinX:
20101218 18:18:05
I think bruteforce can not pass it with 2 second time limit, if the test data is welldesigned. This problem is "E  Dominating Patterns" from ACM ICPC Asia Regional Contest, Hefei 2009/2010. (Even though in the realtime contest KMP algorithm can easily pass.) Last edit: 20101218 19:38:06 

[Trichromatic] XilinX:
20101218 16:21:26
Why not 2 seconds?


Tom Chen:
20101218 15:11:15
I change the time limit to 1.5s...maybe old one is too strict.. 

Tom Chen:
20101218 12:02:26
now testcases are added...sorry for inconvenience... Last edit: 20101218 11:57:00 
Added by:  Tom Chen 
Date:  20101218 
Time limit:  0.100s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem 