E. Clean Substrings
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A binary string $$$t$$$ of length $$$m$$$ is called clean if $$$t_i = t_{i+1}$$$ for all $$$1\le i\lt m$$$.

The chief engineer of the country has made another discovery. He invented a smart robot that can perform the following operation on any binary string $$$t$$$ for one coin:

  • Choose any clean substring$$$^{\text{∗}}$$$ of the string $$$t$$$.
  • Invert all elements of the substring (change $$$0$$$ to $$$1$$$ and vice versa).

Define the beauty of a string $$$t$$$ as the minimum number of coins needed to make it clean. Define the power of a string $$$t$$$ as the sum of the beauties of all its substrings.

You are given a binary string $$$s$$$ of length $$$n$$$. The engineer's competitors are going to modify the string exactly $$$q$$$ times. Each modification is described by one number $$$i$$$. After the modification, $$$s_i$$$ is inverted. Your task is to compute the power of the string $$$s$$$ before and after each modification.

$$$^{\text{∗}}$$$A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n, q\le 2\cdot 10^5$$$) — the length of the binary string and the number of modifications.

The second line of each test case contains the binary string $$$s$$$.

The next $$$q$$$ lines of each test case contain one integer $$$i$$$ ($$$1\le i\le n$$$) — the description of the modifications.

It is guaranteed that the sum of all $$$n$$$ values and the sum of all $$$q$$$ values over all test cases do not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output $$$q + 1$$$ integers separated by spaces — the answer before the modifications and after each modification of the string.

Example
Input
4
3 1
110
2
4 2
1010
1
2
8 4
10101110
3
5
2
3
10 5
1100101110
1
6
10
7
3
Output
2 2 
7 5 5 
36 23 22 25 26 
61 66 41 35 59 60
Note

Consider the first test case.

Before the modifications, the string $$$s$$$ is 110. The power of the string is $$$2$$$:

  • The beauty of substring $$$s[1, 1]$$$ is 0.
  • The beauty of substring $$$s[2, 2]$$$ is 0.
  • The beauty of substring $$$s[3, 3]$$$ is 0.
  • The beauty of substring $$$s[1, 2]$$$ is 0.
  • The beauty of substring $$$s[2, 3]$$$ is 1.
  • The beauty of substring $$$s[1, 3]$$$ is 1.
After the modification, the string $$$s$$$ is 100. Now the power is $$$2$$$:
  • The beauty of substring $$$s[1, 1]$$$ is 0.
  • The beauty of substring $$$s[2, 2]$$$ is 0.
  • The beauty of substring $$$s[3, 3]$$$ is 0.
  • The beauty of substring $$$s[1, 2]$$$ is 1.
  • The beauty of substring $$$s[2, 3]$$$ is 0.
  • The beauty of substring $$$s[1, 3]$$$ is 1.