题目描述

译自 ROI 2025 Day2 T1. Качественный отдых

小明正在一家 IT 公司进行为期 $n$ 天的实习，担任技术支持的角色。他的实习日程安排颇为复杂，工作日和休息日交织在一起。除了固定的休息日，小明还有一些调休日——他可以选择在任意工作日额外休息一天。

不过，小明觉得单独一天的休息远远不够，只有连续两天或以上的休息日才能让他真正放松，称之为充实休假日。

你会收到 $q$ 个关于调休日数量的询问，每个询问对应一个不同的调休天数。你的任务是根据小明的实习日程，计算出在每种调休天数下，小明最多能获得多少个充实休假日。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \le n \le 100\,000, 1 \le q \le n+1)$，分别表示实习天数和询问数量。

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

接下来的 $q$ 行，每行包含一个整数 $k_i$ $(0 \leq k_i \leq n)$，表示第 $i$ 个询问中可用的调休天数。保证每个 $k_i$ 不超过日程中的工作日总数。

输出格式

输出 $q$ 个整数，分别表示在每个 $k_i$ 调休天数下，小明通过选择 $k_i$ 个额外休息日，最多能获得的充实休假日数量。

3 4
000
0
1
2
3

0
0
2
3

4 3
1010
0
1
2

0
3
4

11 6
11010101001
5
2
0
1
4
3

11
7
2
5
10
9

提示

样例解释 1

在第一个样例中，实习的 $3$ 天全是工作日。如果调休少于 $2$ 天，无法获得充实休假日。对于 $k_3 = 2$ 或 $k_4 = 3$，可以选择前 $k_j$ 天作为调休日，这些天都将成为充实休假日。

样例解释 2

在第二个样例中，最优策略是将调休日安排在第二天，这样前三天都将成为充实休假日。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。