Мова#2739

Мова

1 секунда

256 мегабайтів

Дуже складна

Прибувши в Антарктиду, Шкіпер, Ріко, Прапорщик і Ковальські виявили, що не розуміють, про що говорять місцеві пінгвіни. Шкіпер доручив Прапорщику, як найрозумнішому, розібратися з мовою місцевих і отримати від них оперативну інформацію.

Прапорщик записав усі фрази, які почув від місцевих, у послідовності звуків, використовуючи малі латинські літери. Таким чином, він отримав рядок $s$ з $n$ малих латинських літер. Потім Прапорщик почав аналіз цього рядка: змінював символи, переставляв підрядки з місця на місце, порівнював підрядки між собою... Зрештою Прапорщик остаточно заплутався і попросив у вас допомоги. Він ретельно записував усі проведені з рядком операції на аркуші паперу, отримавши список із $m$ записів одного з таких типів:

$S i c$ — Прапорщик замінив літеру на позиції $i$ у рядку на літеру $c$ .
$M i j k$ — Прапорщик вирізав підрядок із позиції $i$ до $j$ вихідного рядка та вставив його після символу на позиції $k$ . Тут число $k$ означає позицію символу у рядку після видалення підрядка $s [i .. j]$ . Якщо $k = 0$ k = 0, це означає, що вирізаний підрядок слід вставити на початок отриманого рядка.
$C i j l$ — Прапорщик порівняв підрядки $s [i .. i + l - 1]$ s[i..i+l-1] та $s [j .. j + l - 1]$ s[j..j+l-1].
$P$ — Прапорщик переписав поточну версію рядка на аркуш результату.

На жаль, Прапорщик загубив аркуш результату, а без нього зрозуміти мову місцевих неможливо. Допоможіть йому відновити результати проведених операцій.

Вхідні дані

У першому рядку вхідних даних задано два числа $n$ і $m$ — довжина рядка, який записав Прапорщик, та кількість виконаних операцій ( $1 \leq n, m \leq 1 0^{5}$ 1 \le n,\ m \le 10^5). У другому рядку задано $n$ малих латинських літер — початковий рядок, записаний Прапорщиком. У наступних $m$ рядках задано описи дій Прапорщика у вказаному вище форматі. Всі індекси гарантовано знаходяться у допустимих межах, а при заданні підрядка $i \leq j$ i \le j.

Символи у рядку нумеруються від $1$ до $n$ , символ на $i$ -й позиції позначається як $s [i]$ . Нагадаємо, що підрядок $s [i .. j]$ з рядка $s$ — це рядок, що складається із символів $s [i]$ , $s [i + 1]$ s[i+1], ..., $s [j]$ .

Вихідні дані

Виведіть по одному рядку для кожної операції порівняння або копіювання. Для кожної операції порівняння, виконаної Прапорщиком, виведіть $"+"$ , якщо підрядки збігалися, інакше — $"-"$ . Для кожної операції копіювання виведіть поточний стан рядка на цей момент. Гарантується, що загальний обсяг виведених даних (без урахування символів переходу на новий рядок) не перевищуватиме одного мегабайта.

Приклади

Приклад 1