H. Безопасность
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Один сайт по программированию налаживает безопасный протокол связи. По соображениям безопасности они хотят выбрать несколько более или менее случайных строк.

Изначально у них есть строка $$$s$$$, состоящая из строчных латинских букв. Затем они хотят выбрать $$$q$$$ строк следуя шагам ниже, а вы должны им помочь.

  1. Выбирается строка $$$x$$$, состоящая из строчных латинских букв и целые числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq |s|$$$).
  2. Рассмотрим все непустые различные подстроки строки $$$s_l s_{l + 1} \ldots s_r$$$, то есть все различные строки $$$s_i s_{i+1} \ldots s_{j}$$$, где $$$l \le i \le j \le r$$$. Среди всех из них оставим только строки, которые лексикографически больше строки $$$x$$$.
  3. Если таких строк нет, то выведите $$$-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$$$.

Входные данные

Первая строка содержит непустую строку $$$s$$$ ($$$1 \leq |s| \leq 10^{5}$$$), состоящую только из строчных латинских букв.

Вторая строка содержит целое $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество строк, которые будут выбраны.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l$$$, $$$r$$$ ($$$1 \leq l \leq r \leq |s|$$$) и непустую строку $$$x$$$, состоящую только из строчных латинских букв. Суммарная длина всех строк $$$x$$$ по всем запросам не превосходит $$$2 \cdot 10^{5}$$$.

Выходные данные

Выведите $$$q$$$ строк, каждая из них должна содержать искомую строку или $$$-1$$$, если подходящих строк не оказалось.

Примеры
Входные данные
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
Примечание

Рассмотрим первый пример.

Строка $$$s$$$ равна «baa». Запросы следующие:

  1. Мы рассматриваем подстроку $$$s_1 s_2$$$ равную «ba». У неё есть подстроки «b», «a» и «ba», так как ни одна из них не больше, чем строка запроса «ba», то ответом является $$$-1$$$.
  2. Мы рассматриваем подстроку «aa». Среди её подстрок только «aa» больше чем строка запроса «a». Поэтому ответом является «aa».
  3. Мы рассматриваем подстроку «ba». Среди «b», «a» and «ba» только «ba» больше чем строка запроса «b», поэтому ответом является «ba».
  4. Мы рассматриваем подстроку «aa». Ни одна из подстрок «aa» не больше, чем строка запроса «aa», поэтому ответом является $$$-1$$$.
  5. Мы рассматриваем подстроку «baa» и у неё (среди прочих) есть подстроки «ba», «baa», которые больше чем строка запроса «b». Так как «ba» лексикографически меньше «baa», то ответом является «ba».