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.