Problem Statement

E869120 the Coder decided to give a string to square1001 as a present each year for the next Q years.
Since E869120's favorite string is S, he also decided to "pick" the string, which he'll give as a present, from S.
Moreover, there's "AtCoder percepts" which has been told from ancient times, so he also decided to determine the string based on this percepts.

The contents of "AtCoder percepts" is as follows:

• When you will give a string as a present, you should decide the string as follows.
• Let T be the set of substring (not necessarily contiguous) of S.
• You should give K-th string of T in lexicographical order.

For example, if his favorite string is aqua, T will be [a,aa,aq,aqa,aqu,aqua,au,aua,q,qa,qu,qua,u,ua]. If K=10, you should give qa as a present, because qa is the 10-th string in T.

However, the value of K will change every year. The i-th year of K will be K_i.
Please answer the last p_i characters of string which you should give to square1001 in i-th year.

Input

Input is given from Standard Input in the following format:

S
Q
K_1 p_1
K_2 p_2
K_3 p_3
...
K_Q p_Q

Output

• Print Q lines.
• In i-th line, print the last p_i characters of substring of the string which he should give in i-th year.
• If there is no string which is applicable, print "-1".
• If the string which he should give is less than p_i characters, print the string. For example, if p_i=7 and string = "abcde", print "abcde".

Sample Input 1

aqua
16
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
10 10
11 10
12 10
13 10
14 10
15 10
16 10

Sample Output 1

a
aa
aq
aqa
aqu
aqua
au
aua
q
qa
qu
qua
u
ua
-1
-1

Please look the example in the problem statement.

Sample Input 2

tourist
2
76 10
76 4

Sample Output 2

tourist
rist

In 2-nd query, the answer is "tourist". But you should output the last 4 characters: "rist", because p_2 = 4.

Sample Input 3

eightsixnineonetwozero
6
869120 100
869120 10
869120 8
869120 6
869120 4
869120 2

Sample Output 3

eihinieonetwoze
ieonetwoze
onetwoze
etwoze
woze
ze