Person in Charge

• SleepingCup

Problem Description

Little Q is playing a turn-based card game called "Absolute Defense" against a computer.

Little Q has a deck of size $n$, containing two types of cards: attack cards and defense cards. At the start of the game, Little Q draws $k \ (1 \le k \le n)$ cards from the top of the deck as his initial hand. He then engages in several rounds of battle with the computer.

At the beginning of each battle round, Little Q draws $2$ cards from the top of the deck. Specifically, if only $1$ card remains in the deck, Little Q draws only that card. Each battle round consists of two turns:

• First turn: Little Q is the attacker, and the computer is the defender.
• Second turn: Little Q is the defender, and the computer is the attacker.

In each turn, the attacker must choose an attack card from their hand to attack, and the defender must play a defense card from their hand to defend. Failure to play the required card results in an immediate loss.

The computer has an unlimited number of attack and defense cards, meaning it can always play the corresponding card. To balance the computer's strength, Little Q can use a special ability: when Little Q is the defender, he can play an attack card from his hand to defend. This ability can be used only once every $3$ battle rounds, meaning that after using the ability, it cannot be used again for the next $2$ battle rounds.

Under these rules, Little Q's goal is to survive the computer's fierce attacks, i.e., to empty the deck at the end of a battle round. Specifically, if the deck is already empty at the start of the game, Little Q immediately achieves his goal. Little Q wants to find the smallest initial draw count $k$ that allows him to achieve the goal.

Little Q finds this problem too simple, so he adds $q$ modification operations. The $i$-th ($1 \le i \le q$) modification operation is given a positive integer $x_i$, which changes the type of the $x_i$-th card from the top to the bottom of the deck, i.e., converting an attack card to a defense card or vice versa. For the initial deck and after each modification, you need to determine the smallest initial draw count $k$ that allows Little Q to achieve the goal.

Input Format

This problem contains multiple test cases.

The first line of input contains two non-negative integers $c$ and $t$, representing the test case ID and the number of test cases, respectively. $c = 0$ indicates a sample test case.

Next, each test case is input sequentially. For each test case:

The first line contains two non-negative integers $n$ and $q$, representing the size of the deck and the number of modifications, respectively.

The second line contains a string $s_1 s_2 \ldots s_n$ of length $n$, where each character represents the type of the $i$-th card from the top to the bottom of the deck. Here, $s_i = 0$ indicates an attack card, and $s_i = 1$ indicates a defense card.

The $(i + 2)$-th line ($1 \le i \le q$) contains a positive integer $x_i$, representing the $x_i$-th card from the top to the bottom of the deck to be modified.

Output Format

For each test case, let the initial answer be $k_0$, and the answer after the $i$-th ($1 \le i \le q$) modification be $k_i$. Output a line with $q+1$ positive integers $k_0, k_1, \ldots, k_q$, representing the smallest initial draw count and its value after each modification that allows Little Q to achieve the goal.

Samples

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

1 1
3
2

Sample 1 Explanation

This sample contains three test cases.

For the first test case:

• Initially, the deck is $01010$. If the initial draw count is $1$, one possible play sequence for Little Q is:

  • Initial hand: $\{0\}$;
  • Draw two cards from the top, play one attack card and one defense card, hand becomes $\{0\}$;
  • Draw two cards from the top, play one attack card and one defense card, hand becomes $\{0\}$, and the deck is now empty.

  Since the minimum initial draw count is $1$, $k_0=1$.

• After the first modification, the deck becomes $01000$. If the initial draw count is $1$, one possible play sequence for Little Q is:

  • Initial hand: $\{0\}$;
  • Draw two cards from the top, play one attack card and one defense card, hand becomes $\{0\}$;
  • Draw two cards from the top, play one attack card and use the special ability to play another attack card for defense, hand becomes $\{0\}$, and the deck is now empty.

  Since the minimum initial draw count is $1$, $k_1=1$.

For the second test case:

If the initial draw count is $3$, one possible play sequence for Little Q is:

• Initial hand: $\{0,0,0\}$;

• Draw two cards from the top, play one attack card and one defense card, hand becomes $\{0,0,0\}$;

• Draw two cards from the top, play one attack card and use the special ability to play another attack card for defense, hand becomes $\{0,0,0\}$, and the deck is now empty.

  It can be proven that no smaller initial draw count can empty the deck, so the answer is $3$.

For the third test case:

If the initial draw count is $2$, one possible play sequence for Little Q is:

• Initial hand: $\{0,0\}$;

• Draw two cards from the top, play one attack card and use the special ability to play another attack card for defense, hand becomes $\{0,1\}$;

• Draw two cards from the top, play one attack card and one defense card, hand becomes $\{0,1\}$;

• Draw two cards from the top, play one attack card and one defense card, hand becomes $\{0,0\}$, and the deck is now empty.

  It can be proven that no smaller initial draw count can empty the deck, so the answer is $2$.

Sample 2

See the files defense/defense2.in and defense/defense2.ans in the contestant's directory.

This sample satisfies the constraints of test case $2$.

Sample 3

See the files defense/defense3.in and defense/defense3.ans in the contestant's directory.

This sample satisfies the constraints of test cases $5 \sim 7$.

Sample 4

See the files defense/defense4.in and defense/defense4.ans in the contestant's directory.

This sample satisfies the constraints of test cases $9,10$.

Sample 5

See the files defense/defense5.in and defense/defense5.ans in the contestant's directory.

This sample satisfies the constraints of test case $11$.

Sample 6

See the files defense/defense6.in and defense/defense6.ans in the contestant's directory.

This sample satisfies the constraints of test cases $12 \sim 14$.

Data Range

Let $N$ and $Q$ be the sums of $n$ and $q$ across all test cases in a single test point, respectively. For all test data, the following guarantees hold:

• $1 \le t \le 10^5$;
• $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$;
• For all $1 \le i \le n$, $s_i \in \{0, 1\}$;
• For all $1 \le i \le q$, $1 \le k_i < n$.

• Special Property $\text{A}$: For all $1 \le i \le n$, $s_i$ is independently and uniformly randomly generated from $\{0,1\}$.
• Special Property $\text{B}$: All $x_i$ are distinct, and for all $1 \le i \le q$, $s_{x_i} = 1$.
• Special Property $\text{C}$: All $x_i$ are distinct, and for all $1 \le i \le q$, $s_{x_i} = 0$.
• Special Property $\text{D}$: For all $1 \le i \le q$, $x_i$ is independently and uniformly randomly generated from $[1, n]$.
• Special Property $\text{E}$: For all $0 \le i < q$, $1 \le k_i \le 45$.