eolymp
bolt
Try our new interface for solving problems
Məsələlər

Подстрока

Подстрока

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Недавно разведка перехватила зашифрованное сообщение — строку s. Все ресурсы аналитического центра, в котором вы работаете, были брошены на его декодирование.

Ваш отдел занимается шифрами нового поколения. На данный момент известно всего n таких шифров. Для каждого из них есть три характерных параметра — целые числа l, r и строка t. Пусть строка g была получена в результате применения этого метода. Тогда строка g_lg_{l+1}...g_{r-1}g_r (здесь g_i — это i-й символ строки g) содержит t как подстроку.

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

Giriş verilənləri

Первая строка входного файла содержит строку s (1 ≤ |s| ≤ 100000, где |s|— длина строки s).

Вторая строка входного файла содержит целое число n — количество типов шифрования (1n100000). Последующие n строк содержат по два целых числа l_i, r_i и строку t, разделенные пробелами — характерные параметры i-го метода шифрования (1 ≤ l_i ≤ r_i ≤ |s|).

Все строки состоят из строчных букв латинского алфавита. Суммарная длина всех t_i не превосходит 100000.

Çıxış verilənləri

Выведите одну строку — для каждого типа шифрования "+", если сообщение s могло быть получено в результате его применения, или "-" в противном случае.

Nümunə

Giriş verilənləri #1
frommarsiam
3
6 10 i
2 11 am
1 9 human
Çıxış verilənləri #1
++-