Kth Smallest Common Substring

Given $n (1 \leq n \leq 10^5)$ strings containing only lowercase letters, you need to find out the $k$th smallest one among all the distinct common substrings of the $n$ strings.

This problem contains multiple test cases.

The first line contains an integer $T$ ($1 \leq T \leq 20$) indicating the number of test cases.

For each test case, the first line of the input contains an integer $n (1 \leq n \leq 10^5)$ indicates the number of the strings.

Each of the next $n$ lines contains a string containing only lowercase letters.

The next line contains an integer $q$, the number of the queries.

Each of the next $q (1 \leq q \leq 10^5)$ lines contains an integer $k (1 \leq k \leq 10^7)$ represeting a query.

It is guaranteed that for each test case, the sum of the length of all strings is no more than $2 \times 10 ^ 5$.

For each query, you need to give an interval $[l,r)$ indicating the first(leftmost) occurrence of the answer in the first string.

If the number of distinct common substrings is less than k, output $-1$ instead.

1
5
abaaaa
aabaab
aabbba
aabaaa
abaabb
3
1
2
3

0 1
2 4
0 2

“红旗杯”第十五届东北地区大学生程序设计竞赛