火山哥在玩一个叫打铁传说的游戏，该游戏有两方：进攻方和防御方，进攻方一共有两种随从：剧毒鱼和小鱼。防守方一共有两种随从：圣盾鱼和大鱼。当两个随从进行战斗时，遵循以下的战斗规则：
- 圣盾鱼与任何鱼交战后，都会变成大鱼
- 大鱼和剧毒鱼交战后会消失，和小鱼交战后不会消失（因为大鱼是真的大！）
现在你是进攻方，你有 $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$