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$ 个额外休息日所能获得的最大高质量休息日数量。
系统评分
| 子任务 | 分值 | $n$ | $q$ | 其他限制 | 依赖子任务 |
|---|---|---|---|---|---|
| 1 | 6 | 所有日子均为工作日 | |||
| 2 | 11 | 休息日与工作日交替，第一天为休息日 | |||
| 3 | 12 | $q=1$ | $k_1=0$ | ||
| 4 | 19 | $q=1$ | $k_1=1$ | ||
| 5 | 11 | $n \leqslant 15$ | 5 | ||
| 6 | 17 | $n \leqslant 1000$ | 5 | ||
| 7 | 13 | 排班表中没有两个连续的休息日 | 1, 2 | ||
| 8 | 11 | 5, 1–7 |
样例
输入格式 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$ 天作为调休，这样它们都将成为高质量休息日。
在第二个样例中，将一个调休安排在第二天是划算的，这样前三天都将成为高质量休息日。