得分: 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 由小写字母组成:来自
atoz. - 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