eolymp
Змагання

Дерево Фенвика

Фенєчка

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

Напишіть програму, яка автоматизує ці перевірки.

Вхідні дані

У першому рядку записано два цілих числа n та k (1n, k100000) - кількість ниток у фенєчці та запитів до програми, відповідно. У другому рядку записано рядок з n символів - кольори ниток у початковому стані. Кожен колір позначається рябковою або прописною буквою латинського алфавіту або цифрою. У наступних k рядках задано запити двох видів:

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

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 122.49 MiB
Вхідні дані #1
7 4
abacaba
? 1 5 3
* 6 c
? 2 6 2
? 3 5 3
Вихідні дані #1
+-+
Джерело 15 Международная олимпиада для школьников ЛКШ для параллелей B,A',A