Один сайт по программированию налаживает безопасный протокол связи. По соображениям безопасности они хотят выбрать несколько более или менее случайных строк.
Изначально у них есть строка \(s\), состоящая из строчных латинских букв. Затем они хотят выбрать \(q\) строк следуя шагам ниже, а вы должны им помочь.
Строка \(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\), если подходящих строк не оказалось.
Рассмотрим первый пример.
Строка \(s\) равна «baa». Запросы следующие:
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
4000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач