Підрядок#1495
Нещодавно було перехоплено зашифроване повідомлення, представлене рядком . Усі ресурси аналітичного центру, в якому ви працюєте, тепер сконцентровані на його розшифруванні.
Ваш відділ спеціалізується на криптографії нового покоління. Зараз відомо шифрів, кожен з яких визначається трьома параметрами: цілими числами , та рядком . Якщо рядок вийшов унаслідок застосування одного з цих шифрів, то підрядок g_lg_{l+1}\ldots g_{r-1}g_r (де g_i — -ий символ рядка ) обов'язково містить як підрядок.
У першому рядку задано рядок (1 \leq |s| \leq 100000, де — довжина рядка ).
У другому рядку міститься одне ціле число — кількість типів шифрувань (1 \leq n \leq 100000). Далі йдуть рядків, кожен з яких містить два цілих числа l_i, r_i та рядок , розділені пробілами, — параметри -го методу шифрування (1 \leq l_i \leq r_i \leq |s|).
Усі рядки складаються з малих латинських літер. Сумарна довжина усіх t_i не перевищує .
Виведіть одним рядком для кожного типу шифрування "+", якщо повідомлення могло бути отримане шляхом застосування цього шифру, або "-" в іншому випадку.
Приклад 1