H - Percepts of Atcoder

Time Limit: 3 sec / Memory Limit: 1024 MB

配点:1400

問題文

E869120 は, 文字列を square1001 に今年から Q 年間, 毎年プレゼントすることにした.
彼は, 文字列 S が大好きであった. そのため, プレゼントする文字列は, 文字列 S から取ることに決めた. また, 古から伝わる, AtCoder 社の教えに基づいて, プレゼントする文字列を決めることにした.
AtCoder 社の教えは, 以下のようなものである.

  • 友達に文字列をプレゼントするときは, 以下の方法で文字列を決めなさい. ここでは, あなたの大好きな文字列を S とおく.
  • 文字列 S の部分列の集合を T とおく. ただし, 文字列 S の部分列とは, S から 0 個以上の文字を取り去ってできた 1 文字以上の長さの文字列のことを指す.
  • 部分列の集合 T を辞書順でソートしたときに, K 番目となる文字列をプレゼントするべきである.

例えば, 大好きな文字列が aqua である場合, T は [a,aa,aq,aqa,aqu,aqua,au,aua,q,qa,qu,qua,u,ua] となる. K=10 のとき, 辞書順で 10 番目となる qa をプレゼントするべきである.

しかし, K の値は年ごとに変わってしまう.
そこで, i 年目の K の値 K_i が与えられるので, 各年ごとのプレゼントすべき文字列の最後の p_i 文字を求めてほしい.

入力

入力は以下の形式で標準入力から与えられる.

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

出力

Q 行出力すること.
i 行目には, i 年目にプレゼントすべき文字列の最後の p_i 文字を出力すること. ただし, 該当する文字列が存在しない場合 "-1" と出力せよ.
また, プレゼントすべき文字列が p_i 文字未満の場合, プレゼントすべき文字列をそのまま出力せよ. 例えば, プレゼントすべき文字列が "abcde" であり, p_i=7 のとき, この行には "abcde" と出力すること.


制約

  • Q1 以上 100 \ 000 以下の整数.
  • S は英小文字から成る, 1 文字以上 300 \ 000 文字以下の文字列.
  • p_i1 以上 |S| 以下の整数.
  • p_1+p_2+...+p_Q \leq 1 \ 000 \ 000
  • K_i1 以上 10^{18} 以下の整数.

小課題

小課題 1 [210 点]

  • Q=1 を満たす.

小課題 2 [320 点]

  • K_i \leq 1 \ 000 \ 000 を満たす.

小課題 3 [870 点]

  • 追加の制約はない.

入力例 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

出力例 1

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

問題文の例の通りです.


入力例 2

tourist
2
76 10
76 4

出力例 2

tourist
rist

2 個目のクエリにおいて, "tourist" の後ろ 4 文字は "rist" なので, これを出力すること.


入力例 3

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

出力例 3

eihinieonetwoze
ieonetwoze
onetwoze
etwoze
woze
ze

score: 1400 points

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".

Constraints

  • 1 \leq Q \leq 100 \ 000.
  • 1 \leq |S| \leq 300 \ 000.
  • S consists of lowercase alphabets: from a to z.
  • 1 \leq p_i \leq |S|.
  • p_1+p_2+...+p_N \leq 1 \ 000 \ 000.
  • 1 \leq K_i \leq 10^{18}.
  • All input values are integers.

Subtasks

Subtask 1 [210 points]

  • Q=1.

Subtask 2 [320 points]

  • K_i \leq 1 \ 000 \ 000.

Subtask 3 [870 points]

  • There is no additional constraints.

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