March 28 ADA University Students + Schoolchildren
Фенечка
Саша находится в процессе творческого поиска. Она хочет сплести ещё одну фенечку, но испытывает сложности при выборе цветов. Сейчас все n ниток, которые она планирует использовать для плетения, выложены в ряд. В процессе размышления Саша время от времени заменяет нитку одного цвета ниткой другого, а также для проверки того, что узор получается тем, который подразумевается, проверяет, что некоторые последовательности цветов ниток равны.
Напишите программу, которая автоматизирует эти проверки.
Входные данные
В первой строке записаны два целых числа n и k - количество ниток в фенечке и запросов к программе, соответственно (1 ≤ n, k ≤ 100000). Во второй строке записана строка из n символов - цвета ниток в начальном состоянии. Каждый цвет обозначается строчной или прописной буквой латинского алфавита или цифрой. В следующих k строках заданы запросы двух видов:
"\* i c" - заменить нитку с номером i на нитку цвета c,
"? i j len" - проверить, равны ли последовательности цветов ниток, начинающиеся в позициях i и j и имеющие длину len.
Выходные данные
Для каждого запроса второго вида выведите "+", если последовательности равны, или "-" в противном случае.
Пример
7 4 abacaba ? 1 5 3 * 6 c ? 2 6 2 ? 3 5 3
+-+