Problem Description

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?

Input

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|$

Output

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

Hint

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.

Author

KUT（DPRK）