Problem G
Pokegene

Image by Let’s Go, Pikachu! and Let’s Go, Eevee!.

Professor Oak, the friendly neighbourhood Pokémon Professor, has been getting a lot of questions about Pokémon ancestors lately.

One of the things a lot of Pokémon trainers are curious about is finding common ancestors of Pokémon in their Pokédex. In particular, each Pokémon Trainer wants to know about the number of Pokémon that are ancestors of exactly $L$ of their Pokémon. The value of $L$, too, is decided by the trainer asking the question.

In Pokémon world, given the genome strings of Pokémon A and Pokémon B, Pokémon A is considered an ancestor of Pokémon B if and only if the genome string of Pokémon A is a prefix of Pokémon B’s genome string. Also, all non-empty genome strings correspond to a real Pokémon in the Pokémon world.

Given Professor Oak’s database of Pokémon genomes, help him answer the trainers’ queries.

Input

The first line of input will contain the integer $N$, ($1 \leq N \leq 200\, 000$), the number of Pokémon in Professor Oak’s database, and the integer $Q$, ($1 \leq Q \leq 200\, 000$), the number of Pokémon trainers that have questions for Professor Oak. The following $N$ lines contain a string, each denoting a Pokémon genome string from Professor Oak’s database. All genome strings are distinct and consist of lowercase English letters.

Then $2 \cdot Q$ lines follow. Two lines describe each Pokémon trainer’s query. The first line of each query contains two integers: $K$, ($1 \leq K \leq N$), the number of Pokémon they own, and $L$, ($1 \leq L \leq K$), the value described in the statement. The second line contains $K$ distinct space-separated integers. An integer $x$ in the list of $K$ integers indicates that this trainer owns the $x$th Pokémon from Professor Oak’s database, where the Pokémon Professor Oak owns are numbered from $1$ to $N$.

The sum of the lengths of the genome strings in input does not exceed $200\, 000$ characters and the sum of $K$ over all queries does not exceed $1\, 000\, 000$.

Output

For each Pokémon trainer’s query, print the number of Pokémon that are ancestors of exactly $L$ of the $K$ Pokémon they own. Assume that all non-empty genome strings correspond to a Pokémon. Note that $L$ is defined in the query, and does not necessarily remain the same for all queries.

Example

There are five Pokémon in Professor Oak’s database: “nib”, “abcd”, “abee”, “abced”, and “nit”. There are two trainers with queries.

The first Pokémon trainer owns Pokémon with genome strings “nib”, “abcd”, “nit”, and “abee”, and would like to know how many ancestors there are of exactly two of her Pokémon. Pokémon with genome strings “a” and “ab” are ancestors of “abcd” and “abee”, and Pokémon with genome strings “n” and “ni” are ancestors of “nib” and “nit”, therefore the answer is $4$.

The second Pokémon trainer owns Pokémon with genome strings “abcd”, “abee”, and “abced”, and would also like to know how many ancestors there are of exactly two of her Pokémon. Only the Pokémon with genome string “abc” is an ancestor of exactly $2$ of the owned Pokémon, “abcd” and “abced”, therefore the answer is $1$.

5 2
nib
abcd
abee
abced
nit
4 2
1 2 5 3
3 2
2 3 4

4
1