Prefix Word Counter

A dictionary service stores a bag of lowercase words (the same word may appear more than once, and each occurrence is stored separately). After all words are stored, you receive a series of prefix queries. For each query string p, report how many stored words have p as a prefix. A word is its own prefix, and the empty query (a blank line) matches every stored word.

Input format

• Line 1: two integers n and q — the number of words to store and the number of queries.
• The next n lines: one word each, consisting only of lowercase English letters (a word may be repeated across lines).
• The next q lines: one query prefix each, consisting only of lowercase English letters (a query line may be empty, meaning the empty prefix).

Output format

Print q lines. Line i is the number of stored words that begin with the i-th query prefix.

Constraints

• 1 ≤ n ≤ 100000
• 1 ≤ q ≤ 100000
• Each word has length between 1 and 20.
• Each query prefix has length between 0 and 20.
• Only lowercase English letters appear.