Prokhor 正在一家 IT 公司进行为期 $n$ 个日历天的实习。由于他在支持部门工作，他的实习期间有着复杂的排班表，包含工作日和休息日。除了原本的休息日外，Prokhor 还有一定数量的“调休”——他可以在任何工作日选择调休，将其变为额外的休息日。

由于在单个休息日无法得到充分的休息，Prokhor 仅将那些属于连续两个或更多休息日序列中的休息日视为“高质量休息日”。

给定 $q$ 个查询，每个查询包含 Prokhor 可以使用的不同调休数量。你的任务是根据给定的实习排班表，为每个查询计算 Prokhor 在实习期间能够获得的最大高质量休息日数量。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \leqslant n \leqslant 100\,000$, $1 \leqslant q \leqslant n+1$)。

第二行包含一个长度为 $n$ 的字符串 $s$，由字符“0”和“1”组成，表示实习排班表。其中“0”表示工作日，“1”表示休息日。

接下来的 $q$ 行，每行包含一个整数 $k_i$ ($0 \leqslant k_i \leqslant n$)，表示第 $i$ 个查询中的调休数量。保证每个 $k_i$ 的值不超过排班表中的工作日总数。

输出格式

输出 $q$ 个整数，对于每个 $k_i$，输出 Prokhor 通过选择 $k_i$ 个额外休息日所能获得的最大高质量休息日数量。

系统评分

样例

输入格式 1

3 4
000
0
1
2
3

输出格式 1

0
0
2
3

输入格式 2

4 3
1010
0
1
2

输出格式 2

0
3
4

输入格式 3

11 6
11010101001
5
2
0
1
4
3

输出格式 3

11
7
2
5
10
9

说明

在第一个样例中，所有三天实习均为工作日。如果调休少于两次，则无法获得高质量休息日。对于 $k_3=2$ 或 $k_4=3$，可以选择前 $k_j$ 天作为调休，这样它们都将成为高质量休息日。

在第二个样例中，将一个调休安排在第二天是划算的，这样前三天都将成为高质量休息日。