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

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

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

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

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

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

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