Problems
Подстрока
Подстрока
Недавно разведка перехватила зашифрованное сообщение --- строку \textbf{s}. Все ресурсы аналитического центра, в котором вы работаете, были брошены на его декодирование.
Ваш отдел занимается шифрами нового поколения. На данный момент известно всего \textbf{n} таких шифров. Для каждого из них есть три характерных параметра --- целые числа \textit{\textbf{l}}, \textbf{r} и строка \textbf{t}. Пусть строка \textbf{g} была получена в результате применения этого метода. Тогда строка \textbf{g_lg_\{l+1\}...g_\{r-1\}g_r} (здесь \textbf{g_i} --- это \textbf{i}-й символ строки \textbf{g}) содержит \textbf{t} как подстроку.
Вам поручено определить для каждого типа шифрования, могло ли сообщение \textbf{s} быть получено в результате его применения.
\InputFile
Первая строка входного файла содержит строку \textbf{s} (\textbf{1} ≤ |\textbf{s}| ≤ \textbf{100000}, где |\textbf{s}|--- длина строки \textbf{s}).
Вторая строка входного файла содержит целое число \textbf{n} --- количество типов шифрования (\textbf{1} ≤ \textbf{n} ≤ \textbf{100000}). Последующие \textbf{n} строк содержат по два целых числа \textit{\textbf{l}}_i, \textbf{r_i} и строку \textbf{t}, разделенные пробелами --- характерные параметры \textbf{i}-го метода шифрования (1 ≤ \textit{\textbf{l}}_i ≤ \textbf{r_i} ≤ |\textbf{s}|).
Все строки состоят из строчных букв латинского алфавита. Суммарная длина всех \textbf{t_i} не превосходит \textbf{100000}.
\OutputFile
Выведите одну строку --- для каждого типа шифрования "+", если сообщение \textbf{s} могло быть получено в результате его применения, или "\textbf{-}" в противном случае.
Input example #1
frommarsiam 3 6 10 i 2 11 am 1 9 human
Output example #1
++-