B'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 <= i <= min(|a|, |b|) ), such that a_i < b_i and for all j ( 1 <= 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 <= q |s| <= q 10^{5} ) consisting of lowercase English letters. The second line contains an integer q ( 1 <= q <= 2 cdot 10^5 ) -- the number of strings to select. Each of the next q lines contains two integers l , r ( 1 <= q l <= q r <= q |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. Consider the first example. The string s is "baa". The queries are as follows. '...