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:

IndicesSubsequenceScore$1$1$0$$2$%%ACcode1%%$0$$1, 2$11$1$$3$%%ACcode3%%$0$$1, 3$10$0$$2, 3$%%ACcode5%%$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:

IndicesSubsequenceScore$1$1$0$$2$%%ACcode1%%$0$$1, 2$11$1$$3$%%ACcode3%%$0$$1, 3$11$1$$2, 3$%%ACcode5%%$1$$1, 2, 3$111$2$

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