spoj#NEXTLEX. Next Lexicographically Greater Substring

Next Lexicographically Greater Substring

 

Consider a string S, consisting of only lowercase alphabets.
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.

Consider a string S, consisting of only lowercase alphabets.

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