CRB and Substrings

Value of a string is defined as the number of distinct substrings of it.
For example, value of “ab” is 3(“a”, “b”, “ab”), and value of “xyx” is 5(“x”, “y”, “xy”, “yx”, “xyx”).
Now CRB has a string s.
For some integer $k$, CRB wants to know $k$-length substring of $s$ which has maximum value. But it seems not so easy. Can you help him?

There are multiple test cases.
The first line contains a string $s$. The next line contains an integer $Q$ denoting the number of queries. Each of the next $Q$ lines contains a single integer $k$.
1 ≤ $|s|$ ≤ $10^{5}$
$s$ consists only of lowercase English letters.
1 ≤ $Q$ ≤ 10
1 ≤ $k$ ≤ $|s|$

For each query $k$, output the string whose value is maximum among all $k$-length substrings of $s$, followed by its value.
If multiple substrings have same maximum value, output the lexicographically smallest one.

baa
2
2
1

ba 3
a 1

Query 1:
2-length substrings are “ba” and “aa”.
Value of “ba” is 3, and value of “aa” is 2.
Query 2:
1-length substrings are “b” and “a”.
Both have value 1, but “a” is lexicographically smaller.

KUT（DPRK）

2015 Multi-University Training Contest 10