NEXTLEX - Next Lexicographically Greater Substring

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

Added by:Vaibhav Gosain
Date:2015-12-17
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem

hide comments
2017-09-01 13:22:23
AC with suffix tree....
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.