JZPGYZ - Sevenk Love Oimaster

no tags 

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

hide comments
dqyz_hwk: 2020-10-30 14:52:17

how to get test case

Agam Gupta: 2019-04-22 10:34:14

Nice problem ;)

imkiller: 2018-05-30 19:46:10

Getting TLE using kmp better algo will be?

Raihat Zaman Neloy: 2016-06-13 12:06:58

10^5 * 600 also passes the TL :) Nice problem to solve :)

Ankita Victor: 2015-06-21 06:54:19

how is the answer to the last test case 1?

Jacob Plachta: 2014-02-13 14:43:10

Some of the constraints regarding sums of string lengths aren't met.

Sotirios Nikoloutsopoulos: 2012-06-18 14:09:37

@Tom Chen , can you tell me why my submission with ID : 7171738 gets WA?

Edit : Now i get TLE , can KMP pass?

Last edit: 2012-06-19 16:12:38
Radhakrishnan Venkataramani: 2011-06-01 00:26:07

Can u tell whats the size of input File ?

张钧瑞: 2011-04-17 03:23:00

The task is so difficult for me to solve~

mike_nzk: 2010-12-20 02:12:47

The question is "how many strings",so you should output the number of strings, not the number of substrings.


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