404415: GYM101502 G Most Common Suffix

You are given n strings, and q queries. For each query i, your task is to find the most common suffix of length x_i, you need to print how common it is.

The suffix i (or the i^th suffix) of a string is a special case of substring that goes from the i^th character of the string up to the last character of the string. For example, the 4^th suffix of "development" is "lopment", the 7^th suffix of "development" is "ment" (0-based indexing).

The first line contains an integer T (1 ≤ T ≤ 75), where T is the number of test cases.

The first line of each test case contains two integers n and q (1 ≤ n, q ≤ 10⁴), where n is the number of strings, and q is the number of queries.

Then n lines follow, each line contains a string s, giving the strings. All strings are non-empty consisting of lowercase English letters.

Then q lines follow, each line contains an integer x (1 ≤ x ≤ m), giving the queries. Where m equals the length of the longest string among the given n strings.

The total length of strings in each test case does not exceed 10⁵.

For each query, print a single line containing the answer.

1
5 4
abccba
abddba
xa
abdcba
aneverknow
1
2
4
3

4
3
1
2

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.