Язык
Прибыв в Антарктиду, Шкипер, Рико, Прапор и Ковальски обнаружили, что совершенно не понимают, о чём им говорят местные пингвины. Шкипер поручил Прапору, как самому умному, разобраться с языком местных, чтобы можно было получать от них оперативные данные.
Недолго думая, Прапор записал все встреченные фразы местных в виде одной длинной последовательности звуков, обозначая звуки строчными латинскими буквами. Таким образом он получил строку s из n строчных латинских букв1. После этого Прапор принялся за анализ этой строки: менял в ней символы, переставлял подстроки из одного места в другое, сравнивал подстроки другс другом... В какой-то момент Прапор окончательно запутался и попросил Вас о помощи. Все операции, проводимые со строкой, Прапор аккуратно записывал на листе бумаги, получив список из m записей следующего вида:
S i c — если Прапор заменил букву на i-той позиции строки на букву c.
M i j k — если Прапор вырезал подстроку исходной строки с i-й позиции по j-ю и переместилеё после символа с номером k. При этом число k задаёт позицию символа в строке после того, как из неё удалили подстроку s[i..j]. Если k = 0, значит вырезанную подстроку требуетсяпоместить в начало результирующей строки.
C i j l — если Прапор сравнил подстроки s[i..i+l-1] и s[j..j+l-1].
P — если Прапор переписал строку, полученную на текущий момент, на листок с результатами.
К сожалению, Прапор потерял листок с результатами, а без него язык местных понять будет невозможно. Помогите ему восстановить результаты проведённых операций.
Входные данные
В первой строке входного файла содержатся два числа n и m — длина строки, записанной Прапором и количество операций, которые он провёл над ней, соответственно (1 ≤ n, m ≤ 10^5). Во второй строке находится n строчных латинских букв — исходная строка, записанная Прапором. Далее m строк содержат описания действий Прапора в формате, указанном выше. Гарантируется, что все индексы лежат в допустимом диапазоне, при задании подстроки i ≤ j.
Символы в строке нумеруются числами от 1 до n, символ, стоящий на i-том месте обозначается s[i]. Напомним, что подстрокой s[i..j] строки s называется строка, составленная из символов s[i], s[i+1] ... s[j].
Выходные данные
Выведите по одной строке для каждой операции сравнения или переписывания. Для каждой операции сравнения, проведённой Прапором, выведите "+", если сравниваемые подстроки оказались равны и "-" в противном случае. Для каждой операции переписывания выведите текущее состояние строки на момент проведения этой операции. Гарантируется, что суммарный объём выводимых данных (без учёта переводов строки) не будет превосходить одного мегабайта.