Условие:
Вам дана строка s из n букв a, b и c.
Назовем подпоследовательность этой строки красивой, если она имеет вид a...a b c...c, причем количество букв a и c должно быть одинаковым (возможно, нулевым). Например, строки «abc»,
«aaabccc» и «b» являются хорошими, а строки «aabc», «cba», «ac» и «abca» хорошими не являются.
Требуется ответить на q запросов. В запросе даются два целых числа l и r. Требуется найти
размер максимальной подпоследовательности подстроки s от l до r включительно, являющейся
красивой.
Формат входных данных
Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 200 000) — длина строки и количество
запросов соответственно.
Вторая строка содержит строку s длины n, состоящую из букв a, b и c.
Следующие q строк содержат два целых числа l и r (1 ≤ l ≤ r ≤ n), задающих запрос на
подстроке s от l до r включительно.
Формат выходных данных
Для каждого запроса выведите одно целое число — максимальный размер красивой подпоследовательности заданной подстроки. Если красивых подпоследовательностей у данной подстроки нет,
выведите 0.
Пример
7 4\nacbabcc
1 7
1 2
1 3
2 6
5
0
1
3
