Last | Moment - onoken

For a binary string$$$^{\text{∗}}$$$ $$$v$$$, the score of $$$v$$$ is defined as the maximum value of

$$$$$$F\big(v, 1, i\big) \cdot F\big(v, i+1, |v|\big)$$$$$$

over all $$$i$$$ ($$$0 \leq i \leq |v|$$$).

Here, $$$F\big(v, l, r\big) = r - l + 1 - 2 \cdot \operatorname{zero}(v, l, r)$$$, where $$$\operatorname{zero}(v, l, r)$$$ denotes the number of $$$\mathtt{0}$$$s in $$$v_lv_{l+1} \ldots v_r$$$. If $$$l \gt r$$$, then $$$F\big(v, l, r\big) = 0$$$.

You are given a binary string $$$s$$$ of length $$$n$$$ and a positive integer $$$q$$$.

You will be asked $$$q$$$ queries.

In each query, you are given an integer $$$i$$$ ($$$1 \leq i \leq n$$$). You must flip $$$s_i$$$ from $$$\mathtt{0}$$$ to $$$\mathtt{1}$$$ (or from $$$\mathtt{1}$$$ to $$$\mathtt{0}$$$). Find the sum of the scores over all non-empty subsequences$$$^{\text{†}}$$$ of $$$s$$$ after each modification query.

Since the result may be large, output the answer modulo $$$998\,244\,353$$$.

Note that the modifications are persistent.

$$$^{\text{∗}}$$$A binary string is a string that consists only of the characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

$$$^{\text{†}}$$$A binary string $$$x$$$ is a subsequence of a binary string $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deleting several (possibly zero or all) characters.

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 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) — the length of the string $$$s$$$ and the number of modification queries, respectively.

The second line contains the binary string $$$s$$$ of length $$$n$$$, consisting of characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

The following $$$q$$$ lines each contain an integer $$$i$$$ ($$$1 \leq i \leq n$$$), indicating that $$$s_i$$$ is flipped from $$$\mathtt{0}$$$ to $$$\mathtt{1}$$$ or from $$$\mathtt{1}$$$ to $$$\mathtt{0}$$$.

It is guaranteed that neither the total sum of all values of $$$n$$$ nor the total sum of all values of $$$q$$$ across all test cases exceeds $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$q$$$ lines, each line containing a single integer — the required sum modulo $$$998\,244\,353$$$.

Note

For the first test case, after the first modification, we have $$$s = \texttt{110}$$$. We can compute the sum of scores over all subsequences as follows:

Indices	Subsequence	Score
$$$1$$$	1	$$$0$$$
$$$2$$$	1	$$$0$$$
$$$1, 2$$$	11	$$$1$$$
$$$3$$$	0	$$$0$$$
$$$1, 3$$$	10	$$$0$$$
$$$2, 3$$$	10	$$$0$$$
$$$1, 2, 3$$$	110	$$$0$$$

Summing up: $$$0+0+1+0+0+0+0 = 1$$$.

After the second modification, we have $$$s = \texttt{111}$$$. We can compute the sum of scores over all subsequences as follows:

Indices	Subsequence	Score
$$$1$$$	1	$$$0$$$
$$$2$$$	1	$$$0$$$
$$$1, 2$$$	11	$$$1$$$
$$$3$$$	1	$$$0$$$
$$$1, 3$$$	11	$$$1$$$
$$$2, 3$$$	11	$$$1$$$
$$$1, 2, 3$$$	111	$$$2$$$

Summing up: $$$0+0+1+0+1+1+2 = 5$$$.

Idx	Name	Rating
A	Breach of Faith	1500
B	Finding OR Sum	1900
C	Binary Subsequence Value Sum	2300
D	Maximum Polygon	3100
E	Another Folding Strip	2700
F	AND x OR	3300
G	RGB Walking	3500

Codeforces Round 1008 (Div. 1)