A. Autocomplete
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Peter Mount and Ryei are in a very close Scrabble match. In the game, they must form words and earn points according to the rules. However, the Scrabble played in the MaratonaCIn is a little different: in this version, only words from a specific predetermined set can be formed.

Ryei realized he wouldn't be able to beat Peter Mount, as he is a master of the game. So, he decided to change his strategy: before trying to play a word, he would test which ones were more promising, that is, those that could be transformed into other words within the allowed set. To do this, given a word, he needs to know how many words, that are in the set, he can create, using the given word as a prefix.

Since Ryei is focused on the game, he asked for your help to create a program to assist him in this task. Can you help him?

Input
  • The first line contains two integers, $$$N$$$ and $$$Q$$$ $$$(1 \leq N, Q \leq 10^5)$$$.
  • The next $$$N$$$ lines contain one word each, formed only by lowercase letters of the English alphabet.
  • The following $$$Q$$$ lines contain one word each, formed only by lowercase letters of the English alphabet.
  • The sum of the lengths of all the provided words does not exceed $$$10^6$$$.
Output
  • For each of the $$$Q$$$ queries, print a single integer on a new line, representing the number of words from the original list that have the query word as a prefix.
Example
Input
4 5
a
ab
abc
abcd
a
aa
ab
abc
abcd
Output
4
0
3
2
1