Log in
SOLVE
LATER
Jayati shared an interesting game for testing memorization power with her friends. The game is:
You will get a list of words and some queries. You will be asked, to find out how many words in the list have a query word as a prefix.
If you will not be able to answer her queries, you will miss a chance to impress her. And at any cost, you want to impress her by answering quickly for each query.
Input Format:
The first line contains N, Q: the number words in list and number of queries.
N lines follow, with words (of the list) consisting of lowercase letters. The sum of their lengths won't be greater than 106.
Q lines follow, with words (queries) consisting of lowercase letters. The sum of their lengths won't be greater than 106.
Output Format:
For each query print the number of words in the list which have actual word as the prefix.
12 6 bulldog dog dogged doggedly doggerel dogma dogmatic dogmatism dogs catastroph catastroph doctor cat dog dogg do doctrinography dogge
