Один сайт по программированию налаживает безопасный протокол связи. По соображениям безопасности они хотят выбрать несколько более или менее случайных строк.
Изначально у них есть строка \(s\), состоящая из строчных латинских букв. Затем они хотят выбрать \(q\) строк следуя шагам ниже, а вы должны им помочь.
- Выбирается строка \(x\), состоящая из строчных латинских букв и целые числа \(l\) и \(r\) (\(1 \leq l \leq r \leq |s|\)).
- Рассмотрим все непустые различные подстроки строки \(s_l s_{l + 1} \ldots s_r\), то есть все различные строки \(s_i s_{i+1} \ldots s_{j}\), где \(l \le i \le j \le r\). Среди всех из них оставим только строки, которые лексикографически больше строки \(x\).
- Если таких строк нет, то выведите \(-1\). Иначе выведите лексикографически минимальную из оставшихся строк.
Строка \(a\) лексикографически меньше строки \(b\), если или \(a\) является префиксом строки \(b\), причем \(a \ne b\), или если существует такая позиция \(i\) (\(1 \le i \le min(|a|, |b|)\)), что \(a_i < b_i\) и для всех \(j\) (\(1 \le j < i\)) \(a_j = b_j\). Здесь \(|a|\) обозначает длину строки \(a\).
Выходные данные
Выведите \(q\) строк, каждая из них должна содержать искомую строку или \(-1\), если подходящих строк не оказалось.
Примечание
Рассмотрим первый пример.
Строка \(s\) равна «baa». Запросы следующие:
- Мы рассматриваем подстроку \(s_1 s_2\) равную «ba». У неё есть подстроки «b», «a» и «ba», так как ни одна из них не больше, чем строка запроса «ba», то ответом является \(-1\).
- Мы рассматриваем подстроку «aa». Среди её подстрок только «aa» больше чем строка запроса «a». Поэтому ответом является «aa».
- Мы рассматриваем подстроку «ba». Среди «b», «a» and «ba» только «ba» больше чем строка запроса «b», поэтому ответом является «ba».
- Мы рассматриваем подстроку «aa». Ни одна из подстрок «aa» не больше, чем строка запроса «aa», поэтому ответом является \(-1\).
- Мы рассматриваем подстроку «baa» и у неё (среди прочих) есть подстроки «ba», «baa», которые больше чем строка запроса «b». Так как «ba» лексикографически меньше «baa», то ответом является «ba».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
baa
5
1 2 ba
2 3 a
1 2 b
2 3 aa
1 3 b
|
-1
aa
ba
-1
ba
|
|
2
|
bacb
4
1 2 ba
2 3 ac
1 3 ac
3 4 c
|
-1
c
b
cb
|
|
3
|
bba
1
1 1 b
|
-1
|