eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Фенечка

Фенечка

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Саша находится в процессе творческого поиска. Она хочет сплести ещё одну фенечку, но испытывает сложности при выборе цветов. Сейчас все n ниток, которые она планирует использовать для плетения, выложены в ряд. В процессе размышления Саша время от времени заменяет нитку одного цвета ниткой другого, а также для проверки того, что узор получается тем, который подразумевается, проверяет, что некоторые последовательности цветов ниток равны.

Напишите программу, которая автоматизирует эти проверки.

Входные данные

В первой строке записаны два целых числа n и k - количество ниток в фенечке и запросов к программе, соответственно (1n, k100000). Во второй строке записана строка из n символов - цвета ниток в начальном состоянии. Каждый цвет обозначается строчной или прописной буквой латинского алфавита или цифрой. В следующих k строках заданы запросы двух видов:

  • "\* i c" - заменить нитку с номером i на нитку цвета c,

  • "? i j len" - проверить, равны ли последовательности цветов ниток, начинающиеся в позициях i и j и имеющие длину len.

Выходные данные

Для каждого запроса второго вида выведите "+", если последовательности равны, или "-" в противном случае.

Пример

Входные данные #1
7 4
abacaba
? 1 5 3
* 6 c
? 2 6 2
? 3 5 3
Выходные данные #1
+-+
Источник 15 Международная олимпиада для школьников ЛКШ для параллелей B,A',A