Consider a string S, consisting of only lowercase letters.

You are given a list of queries, each containing a non-empty string STR.

For each query, you have to output:

Among all substrings of S, the next lexicographically greater substring after STR.

Note: If no such substring of S exists which is lexicographically greater than STR, output -1.

Constraints

1 ≤ |S| ≤ 10⁵

1 ≤ Q ≤ 10⁵

1 ≤ |STR| ≤ 10⁵

summation of |STR| for all Q ≤ 10⁵

Input

First line contains the string S.

The next line contains Q, the number of queries to answer.

The next Q lines contain STR for each query.

Output

Output the answer for each query in a new line.

Example

Input:
dabab
3
ab
abaa
bab
Output:
aba
abab
d

Input:
a
1
a

Output:
-1