Description

a180285 was lucky to be selected as an exchange student from Earth to Planet Meow. He found the roll call before class very interesting.

Suppose there are $n$ Meowians in class, and each Meowian’s name consists of a surname and a given name. The teacher on Planet Meow will choose $m$ strings for roll call. Each time a string is read, if this string is a substring of a Meowian’s surname or given name, then that Meowian must respond.

However, the Meowians’ character encoding is so peculiar that it cannot be represented using ASCII. For convenience, a180285 decides to represent Meowian names as sequences of numbers.

Now, can you help a180285 count how many Meowians respond to each roll call, and after all $m$ roll calls, how many times each Meowian has responded?

Input Format

First, we define how strings on Planet Meow are given:

You are first given a positive integer $l$, the length of the string, followed by $l$ integers. The $i$-th integer $a_i$ denotes the $i$-th character of the string.

The first line contains two integers $n$ and $m$, the number of Meowians and the number of roll calls.
The next $n$ lines each contain two Planet Meow strings given as above, representing the $i$-th Meowian’s surname and given name, respectively.
The next $m$ lines each contain one Planet Meow string, representing a string read by the teacher for roll call.

Output Format

For each string read by the teacher, output one line with a single integer indicating how many Meowians respond.
Then output, on the last line, $n$ space-separated integers; the $i$-th integer is the number of times the $i$-th Meowian has been called.

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

2
1
0
1 2

Hint

Sample 1 Explanation

In fact, if the sample is translated into Earth language, it can be viewed as follows:

2 3
izayoi sakuya
orihara izaya
izay
hara
raiz

Constraints

• For $30\%$ of the testdata, it is guaranteed that $n, m \le 10^3$, the total length of Meowian names does not exceed $4 \times 10^3$, and the total length of roll call strings does not exceed $2 \times 10^3$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \le 5 \times 10^4$, $1 \leq m \le 10^5$, the total length of Meowian names and the total length of roll call strings do not exceed $10^5$ respectively, and the numbers that appear as characters in Meowian strings are at most $10^4$.

Translated by ChatGPT 5