CF1037H Security

某编程网站正在建立一个安全通信协议。出于安全考虑，他们希望选择若干个或多或少随机的字符串。 最初，他们有一个由小写英文字母组成的字符串 $s$。现在他们想通过以下步骤选择 $q$ 个字符串，你需要帮助他们完成。 1. 选择一个由小写英文字母组成的字符串 $x$，以及整数 $l$ 和 $r$（$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 \leq i \leq j \leq r$。在这些子串中，选择所有字典序大于 $x$ 的字符串。 3. 如果没有这样的字符串，输出 $-1$。否则，输出这些字符串中字典序最小的一个。 如果字符串 $a$ 是字符串 $b$ 的前缀且 $a \ne b$，或者存在某个位置 $i$（$1 \leq i \leq \min(|a|, |b|)$），使得 $a_i < b_i$ 且对于所有 $j$（$1 \leq j < i$）都有 $a_j = b_j$，则称字符串 $a$ 的字典序小于字符串 $b$。这里 $|a|$ 表示字符串 $a$ 的长度。

输入的第一行包含一个非空字符串 $s$（$1 \leq |s| \leq 10^{5}$），由小写英文字母组成。 第二行包含一个整数 $q$（$1 \leq q \leq 2 \times 10^5$），表示需要选择的字符串个数。 接下来的 $q$ 行，每行包含两个整数 $l$、$r$（$1 \leq l \leq r \leq |s|$）和一个非空字符串 $x$，$x$ 由小写英文字母组成。所有询问中字符串 $x$ 的总长度不超过 $2 \times 10^5$。

输出 $q$ 行，每行输出一个答案。如果没有满足条件的字符串，输出 $-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"，所以答案为 $-1$。 5. 考虑子串 "baa"，其子串中有 "ba"、"baa" 等大于查询字符串 "b" 的子串。由于 "ba" 的字典序小于 "baa"，所以答案为 "ba"。 由 ChatGPT 4.1 翻译