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^5

1<= Q <=10^5

1<=|STR|<=10^5

summation of |STR| for all Q <=10^5

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