시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 69 | 26 | 16 | 34.043% |
Недавно разведка перехватила зашифрованное сообщение --- строку $s$. Все ресурсы аналитического центра, в котором вы работаете, были брошены на его декодирование.
Ваш отдел занимается шифрами нового поколения. На данный момент известно всего $n$ таких шифров. Для каждого из них есть три характерных параметра --- целые числа $l$, $r$ и строка $t$. Пусть строка $g$ была получена в результате применения этого метода. Тогда строка $g_lg_{l+1} \ldots g_{r-1}g_r$ (здесь $g_i$ --- это $i$-й символ строки $g$) содержит $t$ как подстроку.
Вам поручено определить для каждого типа шифрования, могло ли сообщение $s$ быть получено в результате его применения.
Первая строка входного файла содержит строку $s$ ($1 \le |s| \le 100\,000$, где $|s|$ --- длина строки $s$).
Вторая строка входного файла содержит целое число $n$ --- количество типов шифрования ($1 \le n \le 100\,000$). Последующие $n$ строк содержат по два целых числа $l_i$, $r_i$ и строку $t_i$, разделенные пробелами --- характерные параметры $i$-го метода шифрования ($1 \le l_i \le r_i \le |s|$).
Все строки состоят из строчных букв латинского алфавита. Суммарная длина всех $t_i$ не превосходит $100\,000$.
Выведите одну строку --- для каждого типа шифрования <<+
>>, если сообщение $s$ могло быть получено в результате его применения, или <<-
>> в противном случае.
frommarsiam 3 6 10 i 2 11 am 1 9 human
++-