设 $U$ 是一个长度为 $2m$ 且恰好包含 $m$ 个 0 和 $m$ 个 1 的字符串。我们定义 $f(U)$ 为以下子问题的答案：

考虑圆周上等距分布的 $2m$ 个点，按顺时针方向从 $1$ 到 $2m$ 编号。初始时，每个点上都放有一个球。如果 $U_i = 0$，则点 $i$ 处的球为红色；如果 $U_i = 1$，则该球为蓝色。你可以进行任意次数（包括零次）的以下操作：

• 选择一个球。假设它当前在点 $i$。你可以将其移动到点 $i + 1$ 或 $i - 1$。

这里，点 $2m + 1$ 指的是点 $1$，点 $0$ 指的是点 $2m$。

你的目标是达到这样一种状态：对于每个点 $i$，该点上的红球数量和蓝球数量相等。求达到该目标所需的最少操作次数。

给你一个长度为 $n$ 且由 0 和 1 组成的字符串 $S$。同时给你 $q$ 个询问。每个询问包含两个整数 $l$ 和 $r$。设 $T$ 为 $S$ 从第 $l$ 个字符到第 $r$ 个字符（包含端点）的子串。保证 $T$ 包含相同数量的 0 和 1。计算 $f(T)$。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \times 10^5$）。

第二行包含一个长度为 $n$ 且由 0 和 1 组成的字符串 $S$。

接下来的 $q$ 行描述所有询问。其中的第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示一个询问。保证 $S$ 从 $l$ 到 $r$ 的子串包含相同数量的 0 和 1。

输出格式

对于每个询问，输出单行，包含一个整数，表示答案。

样例

输入样例 1

10 3
1101000110
2 5
6 9
1 10

输出样例 1

2
2
7

输入样例 2

29 10
11000001110001010001100100001
16 21
24 25
6 11
7 12
1 10
14 21
10 11
1 4
14 17
8 21

输出样例 2

5
1
5
5
13
6
1
2
2
15

说明

我们来解释第一个测试样例的第一个询问。此时 $T = 1010$。考虑以 $U = T$ 作为输入的子问题。为了达到目标，以下操作序列是最优的：

• 初始时，红球位于点 $2$ 和点 $4$，蓝球位于点 $1$ 和点 $3$。
• 将蓝球从点 $3$ 移动到点 $2$。
• 将红球从点 $4$ 移动到点 $1$。

因此，$f(T) = 2$。