Dictionary search

Given a set of dictionary rows (s_1, s_2, ..., s_n), and a set of query rows (q_1, q_2, ..., q_m), your task is to determine, for each query row (q_i), how many rows in the dictionary have (q_i) as a prefix.

Specifically, for each query index (i), find the number of indices (t) such that (q_i) is a prefix of (s_t).

Input

The first line contains two integers (n) and (m) ((1 $\le$ n, m $\le$ 10^5)). Each of the following (n) lines contains a non-empty dictionary row (s_i). Each of the subsequent (m) lines contains a non-empty query row (q_i). Note that rows in the set may repeat.

Output

Output (m) integers: the (i)-th integer should be the number of dictionary rows for which (q_i) is a prefix.

Examples