Перекрасить и посчитать

4000 мс · 512 МБ · всё или ничего

Дана строка. Запросы: заменить все символы на отрезке одной и той же буквой; узнать, сколько раз данная буква встречается на отрезке.

Формат ввода

В первой строке $n$ и $q$ ( $1 \le n, q \le 10^5$ ). Во второй — строка из строчных латинских букв. Далее $q$ строк: a l r c — заменить символы на отрезке буквой $c$ , или c l r x — сколько раз буква $x$ встречается на отрезке.

Формат вывода

Для каждого запроса c выведите ответ на отдельной строке.

Примеры

ввод

5 4
abcab
c 1 5 a
a 2 4 z
c 1 5 z
c 1 5 a

вывод

2
3
1

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.