Output Format

Output $Q$ lines, each containing a single integer, the answer to the corresponding query.

6 3
010110
2 5
1 6
1 2

4
6
0

Hint

[Constraints and Notes]

For all testdata, it is guaranteed that $n \leqslant 10^5$, $Q \leqslant 10^5$, $1 \leqslant L < R \leqslant n$, and the $\texttt{01}$ string is randomly generated.

Translated by ChatGPT 5