CF1672H.Zigu Zagu

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.

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.