← 返回题目列表

Codeforces · 1037/H

H. 安全

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

一些编程网站正在建立安全通信协议。出于安全原因,他们想选择几个或多或少随机的字符串。

最初,它们有一个由小写英文字母组成的字符串 $$$s$$$。现在他们想要使用以下步骤选择 $$$q$$$ 字符串,你要帮助他们。

1. 选择由小写英文字母和整数 $$$l$$$ 和 $$$r$$$ 组成的字符串 $$$x$$$ ($$$1 \leq l \leq r \leq |s|$$$)。
2. 考虑 $$$s_l s_{l + 1} \ldots s_r$$$ 的所有非空不同子字符串,即所有不同字符串 $$$s_i s_{i+1} \ldots s_{j}$$$,其中 $$$l \le i \le j \le r$$$。其中选择所有按字典顺序大于 $$$x$$$ 的字符串。
3. 如果没有这样的字符串,则应打印$$$-1$$$。否则打印其中按字典顺序最小的。

字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$,如果 $$$a$$$ 是 $$$b$$$ 和 $$$a \ne b$$$ 的前缀,或者存在这样的位置 $$$i$$$ ($$$1 \le i \le min(|a|, |b|)$$$),使得 $$$a_i < b_i$$$ 并且对于所有 $$$j$$$ ($$$1 \le j < i$$$) $$$a_j = b_j$$$。这里$$$|a|$$$表示字符串$$$a$$$的长度。

输入

输入的第一行包含一个由小写英文字母组成的非空字符串 $$$s$$$ ($$$1 \leq |s| \leq 10^{5}$$$)。

第二行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 要选择的字符串数量。

接下来的 $$$q$$$ 行包含两个整数 $$$l$$$、$$$r$$$ ($$$1 \leq l \leq r \leq |s|$$$) 和一个由小写英文字母组成的非空字符串 $$$x$$$。所有查询的字符串 $$$x$$$ 的总长度不超过 $$$2 \cdot 10^{5}$$$。

输出

输出 $$$q$$$ 行,每行应包含所需的字符串或 $$$-1$$$(如果没有此类字符串)。

示例

输入 #1

baa
5
1 2 ba
2 3 a
1 2 b
2 3 aa
1 3 b

输出 #1

-1
aa
ba
-1
ba

输入 #2

bacb
4
1 2 ba
2 3 ac
1 3 ac
3 4 c

输出 #2

-1
c
b
cb

输入 #3

bba
1
1 1 b

输出 #3

-1

注意

考虑第一个例子。

字符串 $$$s$$$ 是“baa”。查询如下。

1. 我们考虑子串 $$$s_1 s_2$$$ 即“ba”。它有子字符串“b”、“a”和“ba”,因为它们都不大于查询字符串“ba”,所以答案是$$$-1$$$。
2. 我们考虑子字符串“aa”。在其子字符串中,只有“aa”大于查询字符串“a”。所以答案是“aa”。
3. 我们考虑子串“ba”。在“b”、“a”和“ba”中,只有“ba”大于查询字符串“b”,因此答案是“ba”。
4. 我们考虑子字符串“aa”。 “aa”的子字符串都不大于查询字符串“aa”,因此答案为 $$$-1$$$。
5. 我们考虑子字符串“baa”,它具有(除其他外)大于查询字符串“b”的子字符串“ba”、“baa”。由于“ba”按字典顺序小于“baa”,因此答案是“ba”。