Фенєчка
Фенєчка
Саша знаходиться у процесі творчого пошуку. Вона хоче сплести ще одну фенєчку, але виникли складнощі при виборі кольорів. Зараз усі $n$ ниток, які вона планує використовувати для плетіння, викладено у ряд. У процесі роздумів Саша час від часу замінює нитку одного кольору ниткою іншого, а також для перевірки того, що візерунок получається таким, який потрібно, перевіряє, що деякі послідовності кольорів ниток рівні.
Напишіть програму, яка автоматизує ці перевірки.
Вхідні дані
У першому рядку записано два цілих числа $n$ та $k$ ($1$ ≤ $n$, $k$ ≤ $100000$) - кількість ниток у фенєчці та запитів до програми, відповідно. У другому рядку записано рядок з $n$ символів - кольори ниток у початковому стані. Кожен колір позначається великою або маленькою буквою латинського алфавіту або цифрою. У наступних $k$ рядках задано запити двох видів:
- "$*$ i $c$" - замінити нитку з номером $i$ на нитку кольора $c$,
- "$?$ та числа $i$, $j$, $len$" - перевірити, чи рівні послідовності кольорів ниток, які починаються у позиціях $i$ та $j$ і мають довжину $len$.
Вихідні дані
Для кожного запиту другого виду виведіть "$+$", якщо послідовності рівні, або "$-$" у протилежному випадку.
7 4 abacaba ? 1 5 3 * 6 c ? 2 6 2 ? 3 5 3
+-+