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