Most Frequent Substrings

You are given a log string and two integers m and k. Your task is to extract all contiguous substrings of length m from the log string, count the frequency of each substring, and then output the top k substrings sorted by their frequency in non‐increasing order. In case of a tie (i.e. two substrings appear the same number of times), they should be sorted in lexicographical order (i.e. dictionary order).

More formally, let \( S \) be the log string of length \( n \) and let \( m \) be an integer such that \( 1 \le m \le n \). For every index \( i \) with \( 0 \le i \le n-m \), consider the substring \( S[i:i+m] \). Let \( f(x) \) denote the number of occurrences of substring \( x \) in \( S \). You need to output the k substrings with the highest values of \( f(x) \), sorting by \( f(x) \) in descending order and then by \( x \) in ascending lexicographical order if frequencies are equal.

inputFormat

The first line of the input contains an integer \( T \) representing the number of test cases. Each of the following \( T \) lines contains a test case, where each test case consists of:

• an integer \( m \) -- the length of substrings to consider,
• an integer \( k \) -- the number of top substrings to output, and
• a string representing the log.

The values are separated by spaces.

outputFormat

For each test case, output a single line containing the top k substrings (or all unique substrings if there are fewer than k distinct substrings). The substrings should be printed in order (separated by a single space) following the sorting rule described above.

## sample

5
2 3 ababcababa
3 2 abcabcabcabc
1 1 aaaaa
2 5 ababc
5 1 abcde

ab ba bc
abc bca
a
ab ba bc
abcde

</p>