一些编程网站正在建立安全通信协议。出于安全原因,他们想选择几个或多或少随机的字符串。
最初,它们有一个由小写英文字母组成的字符串 $$$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”。