a180285 was lucky enough to be selected as an exchange student from Earth to Meow Planet. He finds the roll call process before classes on Meow Planet very interesting.

Suppose there are $N$ Meow Planet residents in class, and each resident's name consists of a first name and a last name. The teacher on Meow Planet will select $M$ strings for roll call. Each time a string is read, if this string is a substring of a resident's first name or last name, then that resident must answer "present".

However, because the characters on Meow Planet are too strange, they cannot be represented by ASCII codes. For convenience, a180285 decided to use a sequence of integers to represent the names of the Meow Planet residents.

Can you help a180285 count how many residents answer "present" each time a string is read, and how many times each resident has answered "present" after all $M$ roll calls are finished?

Input

The definition of strings on Meow Planet is as follows: First, provide a positive integer $L$, representing the length of the string, followed by $L$ integers representing the characters of the string.

The first line of the input contains two integers $N$ and $M$. The next $N$ lines each contain two strings representing the first name and last name of the $i$-th resident. Both the first name and last name are standard strings on Meow Planet. The next $M$ lines each contain a string on Meow Planet, representing the string read by the teacher for roll call.

Output

For each string read by the teacher, output how many residents should answer "present". Finally, in the last line, output how many times each resident has answered "present".

Examples

Input 1

2 3
6 8 25 0 24 14 8 6 18 0 10 20 24 0
7 14 17 8 7 0 17 0 5 8 25 0 24 0
4 8 25 0 24
4 7 0 17 0
4 17 0 8 25

Output 1

2
1
0
1 2

Note

In fact, the data given in the example can be viewed as follows if translated into Earth's language:

2 3
izayoi sakuya
orihara izaya
izay
hara
raiz

Constraints

For 30% of the data, it is guaranteed that: $1 \le N, M \le 1000$, the total length of the residents' names does not exceed 4000, and the total length of the roll call strings does not exceed 2000.

For 100% of the data, it is guaranteed that: $1 \le N \le 20000$, $1 \le M \le 50000$. The total length of the residents' names and the total length of the roll call strings do not exceed 100000 respectively. It is guaranteed that the number of distinct characters appearing in the Meow Planet strings does not exceed 10000.