小 Q はコンピュータと「絶対防御」と呼ばれるターン制カードゲームをプレイしています。
小 Q には大きさ $n$ のデッキがあり、攻撃カードと防御カードの2種類のカードが含まれています。ゲーム開始時、小 Q はデッキのトップから $k \ (1 \le k \le n)$ 枚のカードを初期手札として引き、その後コンピュータといくつかの対戦ラウンドを行います。
各対戦ラウンドの開始時、小 Q はデッキのトップから $2$ 枚のカードを引きます。特に、デッキに残っているカードが $1$ 枚だけの場合、小 Q は $1$ 枚のみを引きます。1ラウンドの対戦は2つのターンに分かれます：
- 第1ターン：小 Q は攻撃側、コンピュータは防御側；
- 第2ターン：小 Q は防御側、コンピュータは攻撃側。
各ターンにおいて、攻撃側は必ず手札から1枚の攻撃カードを出して攻撃し、防御側は必ず手札から1枚の防御カードを出して防御しなければなりません。要件どおりにカードを出せない場合、直ちに敗北となります。
コンピュータの攻撃カードと防御カードは無限にあります。つまり、各ターンでコンピュータは常に対応するカードを出すことができます。コンピュータの強さを調整するために、小 Q は特殊スキルを1つ使用できます：小 Q が防御側のとき、手札から1枚の攻撃カードを出して防御することができます。このスキルは各 $3$ ラウンドの対戦につき1回のみ使用でき、すなわち、あるラウンドでスキルを使った後、次の $2$ ラウンドではこのスキルを使えません。
与えられたルールの下で、小 Q の勝利条件はコンピュータの激しい攻撃を生き延びること、すなわち、ある対戦ラウンドの終了後にデッキが空になることです。特に、ゲーム開始時にデッキがすでに空であれば、小 Q は即座に勝利条件を満たします。小 Q は、勝利条件を達成できる最小の初期手札枚数 $k$ を知りたいと思っています。
小 Q はこの問題が簡単すぎると考え、$q$ 回の変更操作を追加しました。第 $i \ (1 \le i \le q)$ 回目の変更操作では、正の整数 $x_i$ が与えられ、デッキのトップからデッキのボトムまで数えて $x_i$ 枚目のカードの種類を変更します。すなわち、攻撃カードなら防御カードに、防御カードなら攻撃カードに変えます。初期および各変更後のデッキについて、小 Q が勝利条件を達成できる最小の初期手札枚数 $k$ を求めてください。
入力形式
標準入力からデータを読み込みます。
この問題には複数のテストデータが含まれています。
入力の最初の行には、2つの非負整数 $c, t$ が含まれ、それぞれテストポイント番号とテストデータのグループ数を表します。$c = 0$ はこのテストポイントがサンプルであることを示します。
次に各テストデータグループごとに順に入力します：
最初の行には2つの非負整数 $n, q$ が含まれ、それぞれデッキのサイズと変更回数を表します。
2行目には長さ $n$ の文字列 $s_1 \dots s_n$ が含まれ、デッキのトップからボトムまで各カードを表します。$s_i = 0$ なら $i$ 枚目のカードは攻撃カード、$s_i = 1$ なら防御カードです。
第 $i + 2 \ (1 \le i \le q)$ 行には正の整数 $x_i$ が含まれ、$i$ 回目の変更対象となるカードがデッキのトップからボトムまで数えて $x_i$ 枚目であることを示します。
出力形式
標準出力に出力します。
各テストデータグループについて、初期時の答えを $k_0$、第 $i \ (1 \le i \le q)$ 回目の変更後の答えを $k_i$ として、$k_0, k_1, \dots, k_q$ の $q + 1$ 個の正の整数を1行に出力してください。これは初期時および各変更後に小 Q が勝利条件を達成できる最小の初期手札枚数を表します。
サンプル
入力
0 3
5 1
01010
4
7 0
0001000
10 0
0001010000出力
1 1
3
2解説
このサンプルには合計3つのテストデータグループが含まれています。
第1グループについて：
初期デッキは $01010$ です。初期手札枚数が $1$ の場合、小 Q の一つの可能な出し方は：
- 初期手札は ${0}$；
- デッキトップから2枚引いて、攻撃カード1枚、防御カード1枚を出し、手札は再び ${0}$ になる；
- デッキトップから2枚引いて、攻撃カード1枚、防御カード1枚を出し、手札は再び ${0}$、この時デッキが空になる。
初期には最低でも1枚引く必要があるので、最小初期手札枚数は $1$ となり、$k_0 = 1$。
1回目の変更後、デッキは $01000$ になる。初期手札枚数が $1$ の場合、小 Q の一つの可能な出し方は：
- 初期手札は ${0}$；
- デッキトップから2枚引いて、攻撃カード1枚、防御カード1枚を出し、手札は再び ${0}$ になる；
- デッキトップから2枚引いて、攻撃カード1枚、特殊スキルでさらに攻撃カード1枚を防御として出し、手札は再び ${0}$、この時デッキが空になる。
初期には最低でも1枚引く必要があるので、最小初期手札枚数は $1$ となり、$k_1 = 1$。
第2グループについて：
初期手札枚数が $3$ の場合、小 Q の一つの可能な出し方は：
- 初期手札は ${0, 0, 0}$；
- デッキトップから2枚引いて、攻撃カード1枚、防御カード1枚を出し、手札は ${0, 0, 0}$ のまま；
- デッキトップから2枚引いて、攻撃カード1枚、特殊スキルでさらに攻撃カード1枚を防御として出し、手札は ${0, 0, 0}$ のまま、この時デッキが空になる。
$3$ より小さい初期手札枚数でデッキを空にすることはできないことが証明できるので、答えは $3$。
第3グループについて：
初期手札枚数が $2$ の場合、小 Q の一つの可能な出し方は：
- 初期手札は ${0, 0}$；
- デッキトップから2枚引いて、攻撃カード1枚、特殊スキルでさらに攻撃カード1枚を防御として出し、手札は ${0, 1}$ になる；
- デッキトップから2枚引いて、攻撃カード1枚、防御カード1枚を出し、手札は ${0, 1}$ のまま；
- デッキトップから2枚引いて、攻撃カード1枚、防御カード1枚を出し、手札は ${0, 0}$ になる；
- デッキトップから2枚引いて、攻撃カード1枚、特殊スキルでさらに攻撃カード1枚を防御として出し、手札は ${0, 0}$ になり、この時デッキが空になる。
$2$ より小さい初期手札枚数でデッキを空にすることはできないことが証明できるので、答えは $2$。
サンプル2
ダウンロードディレクトリ 内の ex_2.in と ex_2.ans を参照してください。
このサンプルはテストポイント $2$ の制約条件を満たしています。
サンプル3
ダウンロードディレクトリ 内の ex_3.in と ex_3.ans を参照してください。
このサンプルはテストポイント $5\sim 7$ の制約条件を満たしています。
サンプル4
ダウンロードディレクトリ 内の ex_4.in と ex_4.ans を参照してください。
このサンプルはテストポイント $9, 10$ の制約条件を満たしています。
サンプル5
ダウンロードディレクトリ 内の ex_5.in と ex_5.ans を参照してください。
このサンプルはテストポイント $11$ の制約条件を満たしています。
サンプル6
ダウンロードディレクトリ 内の ex_6.in と ex_6.ans を参照してください。
このサンプルはテストポイント $12\sim 14$ の制約条件を満たしています。
データ範囲
$N, Q$ を1つのテストポイント内のすべてのテストデータの $n, q$ の総和とします。すべてのテストデータについて、次の条件を満たします：
- $1 \le t \le 10^{4}$；
- $1 \le n \le 2 \times 10^{5}$、$N \le 5 \times 10^{5}$；
- $0 \le q \le 2 \times 10^{5}$、$Q \le 5 \times 10^{5}$；
- すべての $1 \le i \le n$ について $s_i \in {0, 1}$；
- すべての $1 \le i \le q$ について $1 \le x_i \le n$。
| テストケース | $n \leq$ | $q \leq$ | $N, Q \leq$ | 特殊性質 |
|---|---|---|---|---|
| $1 $ | $20 $ | $20 $ | $60 $ | なし |
| $2 $ | $10^2 $ | $10^2 $ | $10^3 $ | なし |
| $3 $ | $3,000 $ | $3,000 $ | $10^4 $ | なし |
| $4 $ | $3,000 $ | $3,000 $ | $10^4 $ | なし |
| $5 $ | $10^5 $ | $0 $ | $3 \times 10^5$ | なし |
| $6 $ | $10^5 $ | $0 $ | $3 \times 10^5$ | なし |
| $7 $ | $10^5 $ | $0 $ | $3 \times 10^5$ | なし |
| $8 $ | $2 \times 10^5$ | $200 $ | $5 \times 10^5$ | なし |
| $9 $ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | AB |
| $10$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | AB |
| $11$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | AC |
| $12$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | AD |
| $13$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | AD |
| $14$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | AD |
| $15$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | E |
| $16$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | E |
| $17$ | $10^5 $ | $10^5 $ | $3 \times 10^5$ | E |
| $18$ | $10^5$ | $10^5$ | $3 \times 10^5$ | なし |
| $19$ | $10^5$ | $10^5$ | $3 \times 10^5$ | なし |
| $20$ | $2 \times 10^5$ | $2 \times 10^5$ | $5 \times 10^5$ | なし |
特殊性質A：すべての $1 \le i \le n$ について、$s_i$ は ${0, 1}$ から独立かつ一様ランダムに生成されます。
特殊性質B：すべての $x_i$ は互いに異なり、かつすべての $1 \le i \le q$ について $s_{x_i} = 1$ です。
特殊性質C：すべての $x_i$ は互いに異なり、かつすべての $1 \le i \le q$ について $s_{x_i} = 0$ です。
特殊性質D：すべての $1 \le i \le q$ について $x_i$ は $[1, n]$ から独立かつ一様ランダムに生成されます。
特殊性質E：すべての $0 \le i \le q$ について $1\le k_i \le 45$ です。