E. Book Rewriting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

William recently started studying Shakespeare in his high school English class. However, he is having trouble understanding old English. Every time he comes across an old English word, he searches it up in the dictionary. However, because he has a bad memory, he can only remember the most recent word he searched for.

To help others who struggle with old English, he plans to rewrite all of Shakespeare using modern English. He is very organized and would like to rewrite each word and sentence in order. His friend Anne wants to support him on his journey and has offered to memorize one word for him. If Anne memorizes a word, then William will not have to search it up and can ask Anne instead.

William wants to figure out which word he wants Anne to memorize. As such, for every word $$$w_i$$$, he wants to know how many searches he would have to perform if Anne memorized $$$w_i$$$, and he needs your help.

Input

The first line contains two integers $$$N\ (1 \leq N \leq 10^5)$$$ and $$$M\ (1 \leq M \leq 10^5)$$$ representing the number of words he doesn't know and the number of sentences he needs to rewrite.

The second line contains $$$N$$$ space-separated lowercase words $$$w_i$$$, all distinct, each of which represents a word that William doesn't recognize and has to search up.

The next $$$M$$$ lines each contain space-separated words, each of which represents a sentence that William plans to rewrite. Each sentence consists only of lowercase letters and is terminated with a period. Furthermore, each sentence contains no punctuation other than the period.

It is guaranteed that each string in the input consists of at most 10 characters (excluding punctuation) and that each sentence consists of at least 1 word and at most 10 words.

Output

Output $$$N$$$ integers, one on each line, with the $$$i^\text{th}$$$ integer representing the number of searches William would have to perform if Anne memorized $$$w_i$$$

Examples
Input
3 2
thou thy speakst
speakst thou speakst.
thy speakst thou.
Output
3
4
3
Input
3 3
dost thou lovest
by my sword beatrice thou lovest me.
with my sword ill prove the lie thou speakst.
if thou dost seek to have what thou dost hide.
Output
3
2
4
Note

If Anne memorized the word "thou" in sample 1, then William would do the following actions on each word.

  1. speakst - William would search it up.
  2. thou - William would ask Anne and doesn't need to search it up.
  3. speakst - William remembers the word because it is the most recent word he searched up. Therefore, he doesn't need to search it up.
  4. thy - William would search it up.
  5. speakst - William has forgotten this word because the most recent word he searched was "thy." As such, he would search it up.
  6. thou - William would ask Anne and doesn't need to search it up.

This is a total of 3 searches ("speakst," "thy," "speakst").