# [Solution] Zigu Zagu solution codeforces

Zigu Zagu solution codeforces – You have a binary string 𝑎a of length 𝑛n consisting only of digits 00 and 11.

## [Solution] Zigu Zagu solution codeforces

You are given 𝑞q queries. In the 𝑖i-th query, you are given two indices 𝑙l and 𝑟r such that 1𝑙𝑟𝑛1≤l≤r≤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𝑥𝑦|𝑠|1≤x≤y≤|s|. Let 𝑡t be the substring 𝑡=𝑠[𝑥,𝑦]t=s[x,y]. Then for all 1𝑖|𝑡|11≤i≤|t|−1, the condition 𝑡𝑖𝑡𝑖+1ti≠ti+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 𝑠𝑙,𝑠𝑙+1,,𝑠𝑟sl,sl+1,…,sr.

Input

The first line contains two integers 𝑛n and 𝑞q (1𝑛,𝑞21051≤n,q≤2⋅105)  — the length of the binary string 𝑎a and the number of queries respectively.

The second line contains a binary string 𝑎a of length 𝑛n (𝑎𝑖{0,1}ai∈{0,1}).

Each of the next 𝑞q lines contains two integers 𝑙l and 𝑟r (1𝑙𝑟𝑛1≤l≤r≤n)  — representing the substring of each query.

## [Solution] Zigu Zagu solution codeforces

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

Examples
input

Copy
5 3
11011
2 4
1 5
3 5

output

Copy
1
3
2


## [Solution] Zigu Zagu solution codeforces

input

Copy
10 3
1001110110
1 10
2 5
5 10

output

Copy
4
2
3


## Zigu Zagu solution codeforces

In the first test case,

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