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
![](http://www.facebook.com/sharer.php?s=100&p[url]=https://www.hackerearth.com/practice/data-structures/advanced-data-structures/trie-keyword-tree/practice-problems/algorithm/dummy4-2/&p[images][0]=https://static-fastly.hackerearth.com/static/hackerearth/images/logo/HE_cover.jpg&p[title]=Get your %23programming basics right! Solve this problem and see how good you are!"){kind=link}