您有一个长度为 $$$n$$$ 的二进制字符串 $$$a$$$,仅由数字 $$$0$$$ 和 $$$1$$$ 组成。
您收到 $$$q$$$ 查询。在第 $$$i$$$ 查询中,为您提供两个索引 $$$l$$$ 和 $$$r$$$,使得 $$$1 \le l \le r \le n$$$。
设$$$s=a[l,r]$$$。您可以对$$$s$$$进行以下操作:
1. 选择两个索引 $$$x$$$ 和 $$$y$$$,使得 $$$1 \le x \le y \le |s|$$$。设 $$$t$$$ 为子串 $$$t = s[x, y]$$$。然后对于所有 $$$1 \le i \le |t| - 1$$$,条件 $$$t_i \neq t_{i+1}$$$ 必须成立。请注意,$$$x = y$$$ 始终是有效的子字符串。
2. 从$$$s$$$中删除子字符串$$$s[x, y]$$$。
对于每个 $$$q$$$ 查询,找到使 $$$s$$$ 成为空字符串所需的最少操作数。
请注意,对于字符串 $$$s$$$,$$$s[l,r]$$$ 表示子段 $$$s_l,s_{l+1},\ldots,s_r$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10 ^ 5$$$) — 分别是二进制字符串 $$$a$$$ 的长度和查询次数。
第二行包含长度为 $$$n$$$ 的二进制字符串 $$$a$$$ ($$$a_i \in \{0, 1\}$$$)。
接下来的 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) — 表示每个查询的子字符串。
输出
打印 $$$q$$$ 行,第 $$$i$$$ 行表示第 $$$i$$$ 查询所需的最少操作数。
示例
输入 #1
5 3 11011 2 4 1 5 3 5
输出 #1
1 3 2
输入 #2
10 3 1001110110 1 10 2 5 5 10
输出 #2
4 2 3
注意
在第一个测试用例中,
1. 子串是$$$\texttt{101}$$$,所以我们可以通过一次操作将子串清空。
2. 子串是 $$$\texttt{11011}$$$,所以我们可以对 $$$s[2, 4]$$$ 进行一次操作,将 $$$\texttt{11}$$$ 变为空,然后再使用两次操作将子串清空。
3. 子串是 $$$\texttt{011}$$$,所以我们可以对 $$$s[1, 2]$$$ 进行一次操作,将 $$$\texttt{1}$$$ 变为空,然后再进行一次操作,将子串清空。