Problem Description

Define a good $01$ string $\mathcal{S}$ that satisfies the following conditions:

• $\mathcal{S}$ is non-empty.

• For any prefix $\mathcal {S} [1\dots p] (p \in [1,|\mathcal S|])$, the number of $0$ is not greater than the number of $1$.

• For any suffix $\mathcal S[p\dots |\mathcal{S}|] (p \in [1,|\mathcal S|])$, the number of $0$ is not greater than the number of $1$.

Now you are given a $01$ string $\mathcal{T}$ of length $n$. There are $q$ queries. In each query, you are given a pair $l, r$. Find the length of the longest good $01$ subsequence in $\mathcal{T}[l\dots r]$. If there is no good $01$ subsequence, output $-1$.

Note: A subsequence is a new sequence formed by removing some elements without changing the relative order of the remaining elements.

Input Format

The first line contains two integers $n, q$, representing the length of the $01$ string and the number of queries.

The second line contains a $01$ string of length $n$, representing $\mathcal{T}$.

The next $q$ lines each contain two integers $l, r$, representing one query.

Output Format

Output $q$ lines. Each line contains one integer, representing the answer to each query in order.

10 4
0100101011
1 1
1 5
2 9
1 10

-1
3
7
8

Hint

Sample Explanation

In the first query, the queried string is $0$. No subsequence is good, so the answer is $-1$.

In the second query, the queried string is $01001$. The subsequence $101$ is good and is the longest, so the answer is $3$.

In the third query, the queried string is $10010101$. The subsequence $1010101$ is good and is the longest, so the answer is $7$.

In the fourth query, the queried string is $0100101011$. The subsequence $10101011$ is good and is the longest, so the answer is $8$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \leq l \leq r \leq n \leq 5 \times 10^5$, and $1 \leq q \leq 5 \times 10^5$.

Translated by ChatGPT 5