A11989 | Security

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$ .

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 $q$ lines, each of them should contain the desired string or $-1$ , if there is no such string.