March 28 ADA University Students + Schoolchildren
Фенєчка
Саша знаходиться у процесі творчого пошуку. Вона хоче сплести ще одну фенєчку, але виникли складнощі при виборі кольорів. Зараз усі 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
+-+