Range Reversal - Repovive Standard Round 5 | Repovive

14C. Range Reversal

1500 pts2s256 MB

You are given a binary string $s$ of length $n$ .

For a binary string $x$ , define its badness as the number of indices $i$ such that $1 \le i < |x|$ and $x_i = x_{i+1}$ .

You have to answer $q$ independent queries. In a query $l, r$ , consider only the string $x = s_l s_{l+1} \ldots s_r$ . Characters outside this range do not exist for this query.

You may choose at most one non-empty contiguous substring of $x$ and reverse it. For each query, output the minimum possible badness of $x$ after this operation.

Constraints

$1 \le n, q \le 2 \times 10^5$
$s$ is a binary string of length $n$
$1 \le l_i \le r_i \le n$

Input

The input is given in the following format:

n \quad q

s

\left. \begin{array}{l} l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_q \quad r_q \end{array} \right\}

Output

For each query, output the answer on a separate line.

\left. \begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_q \end{array} \right\}

Samples

Input

Explanation

Reverse positions $2$ through $5$ inside the considered string.

Reverse positions $4$ through $5$ inside the considered string.

Reverse positions $1$ through $2$ inside the considered string.

Reverse positions $7$ through $8$ inside the considered string.

Reverse positions $6$ through $7$ inside the considered string.

Output

You are given a binary string $s$ of length $n$ .

For a binary string $x$ , define its badness as the number of indices $i$ such that $1 \le i < |x|$ and $x_i = x_{i+1}$ .

You have to answer $q$ independent queries. In a query $l, r$ , consider only the string $x = s_l s_{l+1} \ldots s_r$ . Characters outside this range do not exist for this query.

You may choose at most one non-empty contiguous substring of $x$ and reverse it. For each query, output the minimum possible badness of $x$ after this operation.

$1 \le n, q \le 2 \times 10^5$
$s$ is a binary string of length $n$
$1 \le l_i \le r_i \le n$

The input is given in the following format:

n \quad q

s

\left. \begin{array}{l} l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_q \quad r_q \end{array} \right\}

For each query, output the answer on a separate line.

\left. \begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_q \end{array} \right\}

Reverse positions $2$ through $5$ inside the considered string.

Reverse positions $4$ through $5$ inside the considered string.

Reverse positions $1$ through $2$ inside the considered string.

Reverse positions $7$ through $8$ inside the considered string.

Reverse positions $6$ through $7$ inside the considered string.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

14C. Range Reversal

Constraints

Input

Output

Samples

14C. Range Reversal

Constraints

Input

Output

Samples