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.
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.
baa
5
1 2 ba
2 3 a
1 2 b
2 3 aa
1 3 b
-1
aa
ba
-1
ba
bacb
4
1 2 ba
2 3 ac
1 3 ac
3 4 c
-1
c
b
cb
bba
1
1 1 b
-1
Consider the first example.
The string $$$s$$$ is "baa". The queries are as follows.
Name |
---|