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