C. Binary Subsequence Value Sumtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLast | 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 > 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.InputEach 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$$$.OutputFor each test case, output $$$q$$$ lines, each line containing a single integer — the required sum modulo $$$998\,244\,353$$$.ExampleInput33 20101310 30101000110351024 101100110011000010111100024Output1
5
512
768
1536
23068672
NoteFor 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$$$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: IndicesSubsequenceScore$$$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$$$.