题目描述

小 Q 与电脑玩回合制卡牌游戏“绝对防御”，小 Q 有一个大小为 $n$ 的牌堆，包含攻击牌（记为 $0$）与防御牌（记为 $1$），游戏规则如下：

1. 游戏开始时，小 Q 从牌堆顶抽取 $k$（$1 \leq k \leq n$）张牌作为初始手牌。
2. 每轮对战开始时，小 Q 从牌堆顶抽取 $2$ 张牌；若牌堆只剩余 $1$ 张牌，则只抽取 $1$ 张。
3. 每轮对战分为两个回合：
   • 第一回合：小 Q 为攻击方，必须从手牌打出一张攻击牌；电脑为防御方，永远能打出防御牌。
   • 第二回合：小 Q 为防御方，必须从手牌打出一张防御牌；电脑为攻击方，永远能打出攻击牌。
4. 特殊技能：当小 Q 为防御方时，可从手牌打出一张攻击牌进行防御，该技能每 $3$ 轮对战才能使用一次（使用后接下来 $2$ 轮无法使用）。

小 Q 的获胜目标为抽空牌堆（游戏开始时牌堆已空则直接获胜），求最小的初始抽牌数 $k$。

小 Q 增加 $q$ 次修改操作，第 $i$（$1 \leq i \leq q$）次修改操作会给定一个正整数 $x_i$，改变从牌堆顶到牌堆底的第 $x_i$ 张牌的类型（攻击牌与防御牌互换）。需对初始时及每次修改后的牌堆，求出上述最小初始抽牌数 $k$。

输入格式

1. 第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数，$c = 0$ 表示该测试点为样例。
2. 每组测试数据：
   • 第一行包含两个正整数 $n, q$，分别表示牌堆大小与修改次数。
   • 第二行包含一个长度为 $n$ 的字符串 $s_1 \dots s_n$，表示从牌堆顶到牌堆底的每张牌，其中 $s_i = 0$ 为攻击牌，$s_i = 1$ 为防御牌。
   • 第 $i + 2$（$1 \leq i \leq q$）行包含一个正整数 $x_i$，表示第 $i$ 次修改的牌为从牌堆顶到牌堆底的第 $x_i$ 张牌。

输出格式

对于每组测试数据，设初始时的答案为 $k_0$，第 $i$（$1 \leq i \leq q$）次修改后的答案为 $k_i$，输出一行 $q + 1$ 个正整数 $k_0, k_1, \dots, k_q$，表示初始时及每次修改后的最小抽牌数。

样例1

输入

0 3
5 1
01010
4
7 0
0001000
10 0
0001010000

输出

1 1
3
2

样例1解释

该样例共包含三组测试数据：

1. 第一组测试数据（$n = 5$，$q = 1$）：
   • 初始时，牌堆为 $01010$，若初始抽牌数为 $1$，小 Q 可通过特定出牌方式抽空牌堆，且初始至少需抽 $1$ 张牌，故 $k_0 = 1$。
   • 第一次修改后，牌堆变为 $01000$，同理初始抽牌数 $1$ 即可满足，故 $k_1 = 1$。
2. 第二组测试数据（$n = 7$，$q = 0$）：
   • 初始时，牌堆为 $0001000$，初始抽牌数 $3$ 可满足抽空牌堆，且无更小值，故 $k_0 = 3$。
3. 第三组测试数据（$n = 10$，$q = 0$）：
   • 初始时，牌堆为 $0001010000$，初始抽牌数 $2$ 可满足抽空牌堆，且无更小值，故 $k_0 = 2$。

数据范围

• 对于所有 $1 \leq i \leq n$，均有 $s_i \in \{0, 1\}$。
• 对于所有 $1 \leq i \leq q$，均有 $1 \leq x_i \leq n$。
• 设 $N, Q$ 分别为单个测试点内所有测试数据的 $n, q$ 的和，具体限制如下表。

特殊性质说明：

• A：保证对于所有 $1 \leq i \leq n$，$s_i$ 均在 $\{0, 1\}$ 中独立均匀随机生成。
• B：保证所有的 $x_i$ 互不相同，且对于所有 $1 \leq i \leq q$，均有 $s_{x_i} = 1$。
• C：保证所有的 $x_i$ 互不相同，且对于所有 $1 \leq i \leq q$，均有 $s_{x_i} = 0$。
• D：保证对于所有 $1 \leq i \leq q$，$x_i$ 均在 $[1, n]$ 中独立均匀随机生成。
• E：保证对于所有 $0 \leq i \leq q$，均有 $1 \leq k_i \leq 45$。