题目描述

定义一个好的 $01$ 串 $\mathcal{S}$ 满足以下条件：

• $\mathcal{S}$ 非空。

• $\mathcal{S}$ 的任意一个前缀 $\mathcal {S}$$[1\dots p](p\in [1,|$$\mathcal S$$|])$ 中，$0$ 的数量都不多于 $1$ 的数量。

• $\mathcal{S}$ 的任意一个后缀 $\mathcal S$$[p\dots |$$\mathcal{S}$$|](p\in [1,|$$\mathcal S$$|])$ 中，$0$ 的数量都不多于 $1$ 的数量。

现在你得到了一个长度为 $n$ 的 $01$ 串 $\mathcal{T}$，有 $q$ 次询问，每次询问给定一对 $l,r$，求 $\mathcal{T}[l\dots r]$ 中的最长的好的 $01$ 子序列 的长度。若没有好的 $01$ 子序列，则输出 $-1$。

注意：子序列 是指去除某些元素但不破坏余下元素的相对位置而形成的新序列。

输入格式

第一行两个整数 $n,q$，分别表示 $01$ 串的长度和询问次数。

第二行一个长度为 $n$ 的 $01$ 串，表示 $\mathcal{T}$。

接下来 $q$ 行，每行两个整数 $l,r$，表示一次询问。

输出格式

输出 $q$ 行，每行一个整数，依次表示每次询问的答案。

10 4
0100101011
1 1
1 5
2 9
1 10

-1
3
7
8

提示

样例解释

第一次询问中，询问的串为 $0$，没有任何的子序列是好的，所以答案是 $-1$。

第二次询问中，询问的串为 $01001$，子序列 $101$ 是好的且是最长的，所以答案是 $3$。

第三次询问中，询问的串为 $10010101$，子序列 $1010101$ 是好的且是最长的，所以答案是 $7$。

第四次询问中，询问的串为 $0100101011$，子序列 $10101011$ 是好的且是最长的，所以答案是 $8$。

数据规模

本题采用捆绑测试。

对于 $100\%$ 的数据，$1 \leq l \leq r \leq n \leq 5 \times 10^5$，$1 \leq q \leq 5 \times 10^5$。