10811.绝对防御（defense）

小 Q 在与电脑玩一款名为“绝对防御”的回合制卡牌游戏。 小Q有一个大小为n的牌堆，包含两种牌：攻击牌与防御牌。游戏开始时，小Q会从牌堆顶抽取k（1≤k≤n）张牌作为初始手牌，接下来他会与电脑进行若干轮对战。每轮对战开始时，小Q从牌堆顶抽取2张牌。特别地，若牌堆只剩余1张牌，则小Q只抽取1张。一轮对战分为两个回合： ·第一回合：小Q为攻击方，电脑为防御方； ·第二回合：小Q为防御方，电脑为攻击方。 在每回合中，攻击方必须从手牌打出一张攻击牌进行攻击，防御方必须从手牌打出一张防御牌进行防御。无法按要求出牌者立即判负。 电脑的攻击牌与防御牌都是无限的，即每回合中电脑永远能打出对应牌。为平衡电脑的实力，小Q可以使用一种特殊技能：当小Q为防御方时，他可以从手牌打出一张攻击牌进行防御。该技能每3轮对战才能使用一次，即在某轮使用技能后，接下来的2轮对战中均不能使用该技能。 在给定规则下，小Q的获胜目标为在电脑猛烈攻势中存活，即存在某轮对战结束后，牌堆被抽空。特别地，若游戏开始时牌堆已被抽空，则小Q直接达成获胜目标。小Q想知道最小的初始抽牌数k，使得他能达成获胜目标。 小Q觉得这个问题过于简单，因此他增加了q次修改操作。第i（1≤i≤q）次修改操作会给定一个正整数Li，改变从牌堆顶到牌堆底的第Li张牌的类型，即将攻击牌变为防御牌，将防御牌变为攻击牌。你需要对初始时及每次修改后的牌堆，求出最小的初始抽牌数k，使得小Q能达成获胜目标。

从文件defense.in中读入数据。 本题包含多组测试数据。 输入的第一行包含两个非负整数c,t，分别表示测试点编号与测试数据组数。c=0表示该测试点为样例。 接下来依次输入每组测试数据，对于每组测试数据： 第一行包含两个非负整数n,q，分别表示牌堆大小与修改次数。 第二行包含一个长度为n的字符串S₁...S_n，分别表示从牌堆顶到牌堆底的每张牌，其中S_i=0表示第i张牌为攻击牌，S_i=1表示第i张牌为防御牌。 第i+2（1≤i≤q）行包含一个正整数x_i，表示第i次修改的牌为从牌堆顶到牌堆底的第x_i张牌。

输出到文件defense.out中。 对于每组测试数据，设初始时的答案为k₀，第i（1≤i≤q）次修改后的答案为k_i，输出一行q+1个正整数k₀,k₁,...,k_q，表示初始时及每次修改后的最小初始抽牌数，使得小Q能达成获胜目标。

【样例1解释】 该样例共包含三组测试数据。 对于第一组测试数据： ·初始时，牌堆为01010。若初始抽牌数为1，小Q的一种可能的出牌方式为： -初始时手牌为[0]； -从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为[0]； -从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为[0]，此时牌堆被抽空。 由于初始至少需要抽取一张牌，所以最小初始抽牌数为1，故k₀=1。 ·第一次修改后，牌堆变为01000。若初始抽牌数为1，小Q的一种可能的出牌方式为： -初始时手牌为[0]； -从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为[0]； -从堆顶抽取两张牌，打出一张攻击牌，使用特殊技能再次打出一张攻击牌进行防御，手牌变为[0]，此时牌堆被抽空。 由于初始至少需要抽取一张牌，所以最小初始抽牌数为1，故k₁=1。 对于第二组测试数据： 若初始抽牌数为3，小Q的一种可能的出牌方式为： ·初始时手牌为[0,0,0]； ·从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为[0,0,0]； ·从堆顶抽取两张牌，打出一张攻击牌，使用特殊技能再次打出一张攻击牌进行防御，手牌变为[0,0,0]，此时牌堆被抽空。 可以证明，不存在比3更小的初始抽牌数能够抽空牌堆，故答案为3。 对于第三组测试数据： 若初始抽牌数为2，小Q的一种可能的出牌方式为： ·初始时手牌为[0,0]； ·从堆顶抽取两张牌，打出一张攻击牌，使用特殊技能再次打出一张攻击牌进行防御，手牌变为[0,1]； ·从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为[0,1]； ·从堆顶抽取两张牌，打出一张攻击牌，一张防御牌，手牌变为[0,0]； ·从堆顶抽取两张牌，打出一张攻击牌，使用特殊技能再次打出一张攻击牌进行防御，手牌变为[0,0]，此时牌堆被抽空。 可以证明，不存在比2更小的初始抽牌数能够抽空牌堆，故答案为2。

【样例2】 见选手目录下的defense/defense2.in与defense/defense2.ans 该样例满足测试点2的约束条件。

【样例3】 见选手目录下的defense/defense3.in与defense/defense3.ans。 该样例满足测试点5～7的约束条件。

【样例4】 见选手目录下的defense/defense4.in与defense/defense4.ans。 该样例满足测试点9，10的约束条件。

【样例5】 见选手目录下的defense/defense5.in与defense/defense5.ans。 该样例满足测试点11的约束条件。

【样例6】 见选手目录下的defense/defense6.in与defense/defense6.ans。 该样例满足测试点12~14的约束条件。

【数据范围】