← 返回题目列表

AtCoder · s8pc_5_h

H. Atcoder 的感知

中文机器翻译题面 查看原题

得分: 1400 点

问题陈述

E869120 编码员决定每年给 square1001 一根绳子作为礼物 Q 年。
由于 E869120 最喜欢的字符串是 S,他还决定从 S.
而且,自古就有“AtCoder感知”,所以他也决定根据这个感知来确定字符串。

《AtCoder感知》内容如下:

  • 当您赠送绳子作为礼物时,您应该如下决定绳子。
  • 让 T 是子串(不一定是连续的)的集合 S.
  • 你应该给 K- 第一个字符串 T 按字典顺序排列。

例如,如果他最喜欢的字符串是 aqua, T 将是 [a,aa,aq,aqa,aqu,aqua,au,aua,q,qa,qu,qua,u,ua]。如果 K=10,你应该给 qa 作为礼物,因为 qa 是 10- 第一个字符串 T.

然而, K 每年都会改变。 i年 K 将是 K_i.
请回答最后一个 p_i 字符串中的字符,您应该将其赋予 square1001 i第一年。

输入

输入由标准输入按以下格式给出:

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

输出

  • 打印 Q 行。
  • In i第行,打印最后一个 p_i 他应该给出的字符串的子字符串的字符 i第一年。
  • 如果没有适用的字符串,则打印“-1”。
  • 如果他应该给出的字符串小于 p_i 个字符,打印字符串。例如,如果 p_i=7 和字符串 =“abcde”,打印“abcde”。

约束

  • 1 \leq Q \leq 100 \ 000.
  • 1 \leq |S| \leq 300 \ 000.
  • S 由小写字母组成:来自 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}.
  • 所有输入值均为整数。

子任务

子任务 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

In 2-nd查询,答案是“游客”。但你应该输出最后一个 4 字符:“rist”,因为 p_2 = 4.


示例输入 3

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

示例输出 3

eihinieonetwoze
ieonetwoze
onetwoze
etwoze
woze
ze