codeforces#P1672H. Zigu Zagu

    ID: 32902 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>constructive algorithmsdata structuresgreedy*2700

Zigu Zagu

Description

You have a binary string $a$ of length $n$ consisting only of digits $0$ and $1$.

You are given $q$ queries. In the $i$-th query, you are given two indices $l$ and $r$ such that $1 \le l \le r \le n$.

Let $s=a[l,r]$. You are allowed to do the following operation on $s$:

  1. Choose two indices $x$ and $y$ such that $1 \le x \le y \le |s|$. Let $t$ be the substring $t = s[x, y]$. Then for all $1 \le i \le |t| - 1$, the condition $t_i \neq t_{i+1}$ has to hold. Note that $x = y$ is always a valid substring.
  2. Delete the substring $s[x, y]$ from $s$.

For each of the $q$ queries, find the minimum number of operations needed to make $s$ an empty string.

Note that for a string $s$, $s[l,r]$ denotes the subsegment $s_l,s_{l+1},\ldots,s_r$.

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10 ^ 5$)  — the length of the binary string $a$ and the number of queries respectively.

The second line contains a binary string $a$ of length $n$ ($a_i \in \{0, 1\}$).

Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$)  — representing the substring of each query.

Print $q$ lines, the $i$-th line representing the minimum number of operations needed for the $i$-th query.

Input

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10 ^ 5$)  — the length of the binary string $a$ and the number of queries respectively.

The second line contains a binary string $a$ of length $n$ ($a_i \in \{0, 1\}$).

Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$)  — representing the substring of each query.

Output

Print $q$ lines, the $i$-th line representing the minimum number of operations needed for the $i$-th query.

Samples

5 3
11011
2 4
1 5
3 5
1
3
2
10 3
1001110110
1 10
2 5
5 10
4
2
3

Note

In the first test case,

  1. The substring is $\texttt{101}$, so we can do one operation to make the substring empty.
  2. The substring is $\texttt{11011}$, so we can do one operation on $s[2, 4]$ to make $\texttt{11}$, then use two more operations to make the substring empty.
  3. The substring is $\texttt{011}$, so we can do one operation on $s[1, 2]$ to make $\texttt{1}$, then use one more operation to make the substring empty.