Назовем строку красивой, если в ней нет подстроки длины хотя бы \(2\), которая является палиндромом. Напомним, что палиндром — это строка, читающаяся одинаково от первого символа к последнему и от последнего символа к первому. Например, строки a, bab, acca, bcabcbacb являются палиндромами, а строки ab, abbbaa, cccb — нет.
Определим стоимость строки, как минимальное количество операций, чтобы строка стала красивой, если за одну операцию разрешено изменить любой символ строки на одну из первых \(3\) букв латинского алфавита (в нижнем регистре).
Вам задана строка \(s\) длины \(n\), каждый символ строки — одна из первых \(3\) букв латинского алфавита (в нижнем регистре).
Вам предстоит ответить на \(m\) запросов — вычислите стоимость подстроки строки \(s\) с \(l_i\)-й по \(r_i\)-ю позицию включительно.