Consider a string $$$t=t_1t_2\ldots t_m$$$ consisting of the characters 0 and 1. We call the pairs of adjacent characters of the string $$$t$$$ the pairs $$$t_1t_2, t_2t_3, \ldots, t_{m-1}t_m$$$, as well as the pair $$$t_mt_1$$$. The last pair connects the end of the string with its beginning, so exactly $$$m$$$ pairs are considered in total. If the string consists of only one character, the only pair that is considered is $$$t_1 t_1$$$.
We call a string $$$t$$$ cyclically balanced if, among its pairs of adjacent characters, the numbers of pairs 00, 01, 10, and 11 are equal.
The cost of a binary string is the minimum number of characters that need to be inserted into it so that it becomes cyclically balanced. Characters may be inserted in any positions, including before the first and after the last character of the string. It is not allowed to delete or replace the original characters.
You are given a binary string $$$s$$$ and $$$q$$$ queries. In each query, indices $$$l$$$ and $$$r$$$ are given. Find the cost of the substring $$$s_l s_{l+1}\ldots s_r$$$.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the length of the string and the number of queries.
The second line contains $$$s$$$ — a sequence of length $$$n$$$ consisting of the characters 0 and/or 1.
Then follow $$$q$$$ lines; the $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the boundaries of the substring for the corresponding query.
Print $$$q$$$ integers: the $$$i$$$-th integer should be equal to the cost of the substring from the $$$i$$$-th query.
11 7001111000001 81 11 21 43 62 77 11
4 3 2 0 4 2 7
