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 3
hi,I'mChuYuXun..YouaresohandsomethatIfallinlovewithyou
butIloveSevenk..you'dbettergoaway
55555555555
ChuYuXun
you
55555555

Output:
1
2
1

Added by:Tom Chen
Date:2010-12-18
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2010-12-19 22:15:04 Garg Ankit
the last test case in the example above should yield the answer 4(according to me). Can anyone explain how is it 1?
2010-12-19 22:03:18 Robert Gerbicz
After about ~20 sigabrt I've discovered that assert(0<=n&&0<=q); gets also runtime error, what is a big mistake.

It would be good to correct/update the tests.

Last edit: 2010-12-19 22:05:23
2010-12-19 06:29:08 mike_nzk
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: 2010-12-19 06:30:30
2010-12-18 20:41:52 Siarhei Kulik
Can O(total_length_of_question_strings*log(total_length_of_n_strings)) pass or should I search for a better algo?

Last edit: 2010-12-18 20:42:13
2010-12-18 18:18:05 [Trichromatic] XilinX
I think brute-force can not pass it with 2 second time limit, if the test data is well-designed. This problem is "E - Dominating Patterns" from ACM ICPC Asia Regional Contest, Hefei 2009/2010. (Even though in the real-time contest KMP algorithm can easily pass.)

Last edit: 2010-12-18 19:38:06
2010-12-18 16:21:26 [Trichromatic] XilinX
Why not 2 seconds?
[reply]:because I don't want brute-force algorithm to pass it :) so make it as strict as possible

Last edit: 2010-12-18 16:46:42
2010-12-18 15:11:15 Tom Chen
I change the time limit to 1.5s...maybe old one is too strict..
2010-12-18 12:02:26 Tom Chen
now testcases are added...sorry for inconvenience...

Last edit: 2010-12-18 11:57:00
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.