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.

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$.

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.

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$.

Sample Input 1 | Sample Output 1 |
---|---|

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