Pokegene

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

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

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

Given Professor Oak's database of Pokemon genomes, help him answer the trainers' queries.

The first line of input contains the integer N, (1 ≤ N ≤ 200 000), the number of Pokemon in Professor Oak's database, and the integer Q, (1 ≤ Q ≤ 200 000), the number of Pokemon trainers that have questions for Professor Oak. The following N lines contain a string, each denoting a Pokemon genome string from Professor Oak's database. All genome strings are distinct and consist of lowercase English letters.

Then 2 · Q lines follow. Two lines describe each Pokemon trainer's query. The first line of each query contains two integers: K, (1 ≤ K ≤ N), the number of Pokemon they own, and L, (1 ≤ L ≤ 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 xth Pokemon from Professor Oak's database, where the Pokemon 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 Pokemon trainer's query, print the number of Pokemon that are ancestors of exactly L of the K Pokemon they own. Assume that all non-empty genome strings correspond to a Pokemon. Note that L is defined in the query, and does not necessarily remain the same for all queries.

There are five Pokemon in Professor Oak's database: "nib", "abcd", "abee", "abced", and "nit". There are two trainers with queries.

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

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