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, and then he will play several rounds of duels against the computer.

At the start of each duel, Little Q draws $2$ cards from the top of the deck. In particular, if only one card remains, he draws just one card. Each duel consists of two turns:

• In the first turn: Little Q is the attacker, and the computer is the defender;
• In the second turn: Little Q is the defender, and the computer is the attacker.

In each turn, the attacker must play an attack card from their hand to attack, and the defender must play a defense card from their hand to defend. Whoever fails to play the required card immediately loses.

The computer has infinite attack and defense cards, so it can always play the required card. To balance the computer’s strength, Little Q has a special skill: when he is the defender, he may play an attack card from his hand to defend. This skill can only be used once every 3 duels; that is, after using it in a duel, he cannot use it in the next 2 duels.

Under these rules, Little Q’s goal is to survive the computer’s onslaught, i.e., to reach a state where the deck is empty at the end of some duel. In particular, if the deck is empty at the start of the game, Little Q immediately achieves this goal. Little Q wants to know the minimum initial draw size $k$ such that he can achieve this goal.

Little Q thinks this problem is too easy, so he adds $q$ modification operations. In the $i\ (1 \le i \le q)$-th modification, a positive integer $x_i$ is given, and the type of the card at position $x_i$ from the top of the deck is changed (attack ↔ defense). You need to compute, for the initial deck and after each modification, the minimum initial draw size $k$ that allows Little Q to achieve his victory condition.

Input Format

Read from standard input.

This problem contains multiple test cases.

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

Then for each test case:

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

The second line contains a string $s_1 \dots s_n$ of length $n$, representing the cards from the top to the bottom of the deck, where $s_i = 0$ indicates the $i$-th card is an attack card, and $s_i = 1$ indicates a defense card.

For $1 \le i \le q$, the $(i+2)$-th line contains a positive integer $x_i$, denoting that in the $i$-th modification, the card at position $x_i$ from the top of the deck is toggled.

Output Format

Print to standard output.

For each test case, let $k_0$ be the answer for the initial deck, and for $1 \le i \le q$, let $k_i$ be the answer after the $i$-th modification. Output a line with $q + 1$ positive integers $k_0, k_1, \dots, k_q$, denoting the minimum initial draw size needed for Little Q to achieve his goal initially and after each modification.

Sample

Input

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

Output

1 1
3
2

Explanation

This sample contains three test cases.

For the first test case:

• Initially, the deck is $01010$. If the initial draw size is $1$, one possible play sequence is:

  • The initial hand is ${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 empty.

  Since at least one card must be drawn at the start, the minimum initial draw size is $1$, so $k_0 = 1$.

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

  • The initial hand is ${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 skill to play another attack card for defense, hand becomes ${0}$, and the deck is empty.

  Hence the minimum initial draw size remains $1$, so $k_1 = 1$.

For the second test case:

• If the initial draw size is $3$, one possible play sequence is:

  • The initial hand is ${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 skill to play another attack card for defense, hand becomes ${0,0,0}$, and the deck is empty.

  It can be shown that no smaller initial draw size suffices, so the answer is $3$.

For the third test case:

• If the initial draw size is $2$, one possible play sequence is:

  • The initial hand is ${0,0}$;
  • Draw two cards from the top, play one attack card and use the special skill to play one 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}$;
  • Draw two cards from the top, play one attack card and use the special skill to play one attack card for defense, hand becomes ${0,0}$, and the deck is empty.

  It can be shown that no smaller initial draw size suffices, so the answer is $2$.

Sample 2

See ex_2.in and ex_2.ans in the download directory.

This sample satisfies the constraints for test point 2.

Sample 3

See ex_3.in and ex_3.ans in the download directory.

This sample satisfies the constraints for test points 5–7.

Sample 4

See ex_4.in and ex_4.ans in the download directory.

This sample satisfies the constraints for test points 9,10.

Sample 5

See ex_5.in and ex_5.ans in the download directory.

This sample satisfies the constraints for test point 11.

Sample 6

See ex_6.in and ex_6.ans in the download directory.

This sample satisfies the constraints for test points 12–14.

Data Range

Let $N,Q$ be the sum of $n$ and $q$ over all test cases in a single test point. It is guaranteed that:

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

Special Property A: It is guaranteed that for all $1 \le i \le n$, each $s_i$ is generated independently and uniformly at random from ${0,1}$.

Special Property B: It is guaranteed that all $x_i$ are distinct, and for all $1 \le i \le q$, $s_{x_i} = 1$.

Special Property C: It is guaranteed that all $x_i$ are distinct, and for all $1 \le i \le q$, $s_{x_i} = 0$.

Special Property D: It is guaranteed that for all $1 \le i \le q$, each $x_i$ is generated independently and uniformly at random from $[1,n]$.

Special Property E: It is guaranteed that for all $0 \le i \le q$, $1 \le k_i \le 45$.