Security
Contest: Manthan, Codefest 18 (rated, Div. 1 + Div. 2)
Difficulty rating: 3200
Tags: data structures, string suffix structures

Some programming website is establishing a secure communication protocol. For security reasons, they want to choose several more or less random strings.

Initially, they have a string $$$s$$$ consisting of lowercase English letters. Now they want to choose $$$q$$$ strings using the following steps, and you are to help them.

1. A string $$$x$$$ consisting of lowercase English letters and integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq |s|$$$) are chosen.
2. Consider all non-empty distinct substrings of the $$$s_l s_{l + 1} \ldots s_r$$$, that is all distinct strings $$$s_i s_{i+1} \ldots s_{j}$$$ where $$$l \le i \le j \le r$$$. Among all of them choose all strings that are lexicographically greater than $$$x$$$.
3. If there are no such strings, you should print $$$-1$$$. Otherwise print the lexicographically smallest among them.

String $$$a$$$ is lexicographically less than string $$$b$$$, if either $$$a$$$ is a prefix of $$$b$$$ and $$$a \ne b$$$, or there exists such a position $$$i$$$ ($$$1 \le i \le min(|a|, |b|)$$$), such that $$$a_i < b_i$$$ and for all $$$j$$$ ($$$1 \le j < i$$$) $$$a_j = b_j$$$. Here $$$|a|$$$ denotes the length of the string $$$a$$$.

Input format:
The first line of input contains a non-empty string $$$s$$$ ($$$1 \leq |s| \leq 10^{5}$$$) consisting of lowercase English letters.

The second line contains an integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of strings to select.

Each of the next $$$q$$$ lines contains two integers $$$l$$$, $$$r$$$ ($$$1 \leq l \leq r \leq |s|$$$) and a non-empty string $$$x$$$ consisting of lowercase English letters. The total length of strings $$$x$$$ for all queries does not exceed $$$2 \cdot 10^{5}$$$.

Output format:
Output $$$q$$$ lines, each of them should contain the desired string or $$$-1$$$, if there is no such string.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
Consider the first example.

The string $$$s$$$ is "baa". The queries are as follows.

1. We consider the substring $$$s_1 s_2$$$ that is "ba". It has substrings "b", "a" and "ba", since none of them is greater than the query string "ba", the answer is $$$-1$$$.
2. We consider substring "aa". Among its substrings only "aa" is greater than the query string "a". So the answer is "aa".
3. We consider substring "ba". Out of "b", "a" and "ba" only "ba" is greater than the query string "b", so the answer is "ba".
4. We consider substring "aa". No substring of "aa" is greater than the query string "aa" so the answer is $$$-1$$$.
5. We consider substring "baa" and it has (among others) substrings "ba", "baa" which are greater than the query string "b". Since "ba" is lexicographically smaller than "baa", the answer is "ba".

Example input:
baa
5
1 2 ba
2 3 a
1 2 b
2 3 aa
1 3 b

Example output:
-1
aa
ba
-1
ba

Example input:
bacb
4
1 2 ba
2 3 ac
1 3 ac
3 4 c

Example output:
-1
c
b
cb

Editorial:
The solution does the following:
1. Build the suffix tree of the whole string (we can construct a suffix tree in $$$O(|S|log|S|)$$$ time using Suffix Array and LCP Array or in O($$$|S|$$$) using any well known algorithm like Ukkonen's algorithm).
2. Note that in a suffix tree, any path from root to leaf is a suffix of the given string. Since we have appended an additional character at the end of S, whose ascii value is smaller than all the literals of string $$$S$$$, we have $$$|S| + 1$$$ leaves in our suffix tree.
3. For example consider the suffix tree of $$$aabcaba$$$. It will look like image shown.
4. Create appropriate type segment tree for the leaves from left to right storing starting position of that leaves.
i.e segment tree for $$$S = aabcaba$$$ is $$$[7, 6, 0, 4, 1, 5, 2, 3]$$$ (starting positions are using 0 based indexing for string S).
5. To answer the request $$$L R X$$$, start descending with this string in the suffix tree from root. To make the larger string we can end the descent process and go on the other edge (which contains a larger symbol), to do this we need to have at least one valid suffix in this subtree -
Valid suffix: it's beginning $$$i$$$ should be $$$L \leq i$$$, $$$i \leq R$$$ and if you stand in the vertex of subtree with length $$$len$$$, then $$$i + len \leq R$$$, that is $$$i \leq R - len$$$.
So the request is too see if any leaf in subtree of matching character from current node has at least on value $$$L \leq i \leq R-len$$$.
The rest is to handle the descent, i.e for example if going to a node with match character from current node, in the middle if we encounter the character to be greater than corresponding character of X, then we will stop the descent process, or if the character of S is smaller than corresponding character of X, then we must ascend till we find a node having valid suffix and matching character greater than corresponding character of S.
Complexity of the solution is $$$O(|x|log(n)*26)$$$ per request.
Consider processing the query for $$$S = aabcaba$$$:
2 5 abca
Modify for 0 based indexes i.e. 1 4 abca
Matching character a, $$$1 \leq i \leq 5$$$: The node 3 matches with a, its subtree have leaves with [6,0,4,1] values and [1,4] are acceptable, so we can ascend.
Matching character b, $$$1 \leq i \leq 4$$$: The node 6 matches with b, its subtree have leaves with [4,1] both are acceptable values for i, so we can ascend to node 6.
Matching character c, $$$1 \leq i \leq 3$$$: The node 8 matches with c, has leaf with value 1, and it is valid, now we start matching subsequent characters to reach node 8,
match c, $$$1 \leq i \leq2$$$
match a, $$$1 \leq i \leq1$$$
match $ , $$$1 \leq i \leq 0$$$ (can't match so start ascent process)
Current node 6: No node with character > c exists, so move to its parent 3.
Current node 3: No node with character > b exists, so move to its parent 1.
Current node 1: Node 9 has starting character b, which is greater than a, also the subtree of node 9 contains leaves with values [5,2], $$$1 \leq i \leq 5$$$, so we can take b and print the currently traversed string so far.