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