Рассмотрим строку $$$t=t_1t_2\ldots t_m$$$, состоящую из символов 0 и 1. Назовём парами соседних символов строки $$$t$$$ пары $$$t_1t_2, t_2t_3, \ldots, t_{m-1}t_m$$$, а также пару $$$t_mt_1$$$. Последняя пара соединяет конец строки с её началом, поэтому всего рассматривается ровно $$$m$$$ пар. Если в строке только один символ, рассматривается только пара $$$t_1 t_1$$$.
Назовём строку $$$t$$$ циклически сбалансированной, если среди её пар соседних символов количества пар 00, 01, 10 и 11 одинаковы.
Стоимостью бинарной строки назовём минимальное количество символов, которые нужно вставить в неё, чтобы она стала циклически сбалансированной. Вставлять символы разрешается в любые позиции, в том числе перед первым и после последнего символа строки. Удалять или заменять исходные символы нельзя.
Дана бинарная строка $$$s$$$ и $$$q$$$ запросов. В каждом запросе заданы индексы $$$l$$$ и $$$r$$$. Найдите стоимость подстроки $$$s_l s_{l+1}\ldots s_r$$$.
Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — длину строки и количество запросов.
Вторая строка содержит $$$s$$$ — последовательность длины $$$n$$$, состоящую из символов 0 и/или 1.
Далее следуют $$$q$$$ строк; $$$i$$$-я из них содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — границы подстроки для очередного запроса.
Выведите $$$q$$$ целых чисел: $$$i$$$-е число должно быть равно стоимости подстроки из $$$i$$$-го запроса.
11 7001111000001 81 11 21 43 62 77 11
4 3 2 0 4 2 7
