408477: GYM103145 L k-th 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