Problem Description

E869120 decided to present a string to square1001 every year for the next $Q$ years.
He loved the string $S$ very much. Therefore, he decided that the strings to be presented would be taken from the string $S$. Also, following the teachings of AtCoder Inc., he decided to determine the strings to be presented.
The teachings of AtCoder Inc. are as follows:

• When presenting a string to a friend, determine the string using the following method. Here, let your favorite string be $S$.
• Let the set of subsequences of string $S$ be $T$. A subsequence of string $S$ refers to a string formed by removing zero or more characters from $S$ to result in a string of one or more characters.
• The string that should be presented is the $K$-th string in lexicographical order when the set of subsequences $T$ is sorted lexicographically.

For example, if the favorite string is aqua, $T$ would be \[`a`,`aa`,`aq`,`aqa`,`aqu`,`aqua`,`au`,`aua`,`q`,`qa`,`qu`,`qua`,`u`,`ua`\]. When $K=10$, the 10th string in lexicographical order, qa, should be presented.

However, the value of $K$ changes every year.
Therefore, given the value of $K$ for each year $i$, $K_i$, you are asked to find the last $p_i$ characters of the string that should be presented each year.

Input Format

The input is given from the 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 Format

Output $Q$ lines.
The $i$-th line should contain the last $p_i$ characters of the string that should be presented in the $i$-th year. If no such string exists, output "-1".
Also, if the string to be presented is shorter than $p_i$ characters, output the entire string. For example, if the string to be presented is "abcde" and $p_i=7$, output "abcde".

Sample Input and Output

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

Sample Input #2

tourist
2
76 10
76 4

Sample Output #2

tourist
rist

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

Notes/Hints

Constraints

• $Q$ is an integer between $1$ and $100,000$ inclusive.
• $S$ is a string consisting of lowercase English letters, with a length between $1$ and $300,000$ characters inclusive.
• $p_i$ is an integer between $1$ and $|S|$ inclusive.
• $p_1 + p_2 + ... + p_Q \leq 1,000,000$
• $K_i$ is an integer between $1$ and $10^{18}$ inclusive.

Subtasks

Subtask $1$ \[$210$ points\]

• $Q=1$ is satisfied.

Subtask $2$ \[$320$ points\]

• $K_i \leq 1,000,000$ is satisfied.

Subtask $3$ \[$870$ points\]

• No additional constraints.

Sample Explanation 1

This is as described in the problem statement.

Sample Explanation 2

In the second query, the last $4$ characters of "tourist" are "rist", so output this.

见题面 Input 部分

见题面 Output 部分