火山哥在玩一个叫打铁传说的游戏，该游戏有两方：进攻方和防御方，进攻方一共有两种随从：剧毒鱼和小鱼。防守方一共有两种随从：圣盾鱼和大鱼。当两个随从进行战斗时，遵循以下的战斗规则：

1. 圣盾鱼与任何鱼交战后，都会变成大鱼
2. 大鱼和剧毒鱼交战后会消失，和小鱼交战后不会消失（因为大鱼是真的大！）

现在你是进攻方，你有 $n$ 个随从，游戏的流程是这样的：一共进行 $K$ 次攻击，第 $i$ 次攻击是你指定你的第 $i$ 个随从去和对方任意一个还存在的随从交战（在对方没有随从时，也可以不交战）。

现在按顺序给定你的 $n$ 个随从，现在你需要对于每个询问 $(X,K)$ 回答：如果游戏一共进行 $K$ 次攻击，且对方有 $X$ 个大鱼，那么对方最多有几个圣盾鱼使得你能把对方所有的鱼都消灭。也就是询问最大的 $Y$，使得如果对方的随从是 $X$ 个大鱼和 $Y$ 个圣盾鱼时，你能把它们全部消灭。

输入格式

第一行两个正整数 $n,Q$，表示你的随从个数和询问个数

第二行一个长度为 $n$ 的 $01$ 串，第 $i$ 个为 $1$ 表示你的第 $i$ 个随从为剧毒鱼，否则为小鱼

接下来 $Q$ 行，每行两个整数 $X,K$ 表示一次询问

输出格式

对于每个询问输出一行一个数，表示 $Y$ 的最大值，如果对方只有 $X$ 个大鱼时你都无法完全消灭它们的话，输出 $-1$

样例数据

样例输入

6 5
110110
0 6
0 3
1 6
2 6
3 6

样例输出

2
1
2
1
1

子任务

Task1 (8pts)：$1\leq n,Q\leq 100$

Task2(12pts)：$1\leq n,Q\leq 5000$

Task3(12pts)：$X=0$

Task4(26pts)：$K=n$

Task5(22pts)：$1\leq n,Q\leq 10^5$

Task6(20pts)：$1\leq n,Q\leq 4\times 10^5$，$0\leq X\leq n$，$1\leq K\leq n$