D. Скажите палиндромам - нет!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем строку красивой, если в ней нет подстроки длины хотя бы $$$2$$$, которая является палиндромом. Напомним, что палиндром — это строка, читающаяся одинаково от первого символа к последнему и от последнего символа к первому. Например, строки a, bab, acca, bcabcbacb являются палиндромами, а строки ab, abbbaa, cccb — нет.

Определим стоимость строки, как минимальное количество операций, чтобы строка стала красивой, если за одну операцию разрешено изменить любой символ строки на одну из первых $$$3$$$ букв латинского алфавита (в нижнем регистре).

Вам задана строка $$$s$$$ длины $$$n$$$, каждый символ строки — одна из первых $$$3$$$ букв латинского алфавита (в нижнем регистре).

Вам предстоит ответить на $$$m$$$ запросов — вычислите стоимость подстроки строки $$$s$$$ с $$$l_i$$$-й по $$$r_i$$$-ю позицию включительно.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — длина строки $$$s$$$ и количество запросов.

Вторая строка содержит строку $$$s$$$, она состоит из $$$n$$$ символов, каждый из которых является одной из первых $$$3$$$ латинских букв.

Следующие $$$m$$$ строк содержат два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — параметры $$$i$$$-го запроса.

Выходные данные

Для каждого запроса выведите одно целое число — стоимость подстроки строки $$$s$$$ с $$$l_i$$$-й по $$$r_i$$$-ю позицию включительно.

Пример
Входные данные
5 4
baacb
1 3
1 5
4 5
2 3
Выходные данные
1
2
0
1
Примечание

Рассмотрим запросы в примере из условия.

  • в первом запросе интересующая нас подстрока — baa, ее можно превратить в bac за одну операцию;
  • во втором запросе интересующая нас подстрока — baacb, ее можно превратить в cbacb за две операции;
  • в третьем запросе интересующая нас подстрока — cb, ее можно оставить без изменений;
  • в четвертом запросе интересующая нас подстрока — aa, ее можно превратить в ba за одну операцию.