C. 二进制子序列价值之和
每个测试的时间限制：3 秒
内存限制：256 MB

Last | Moment - onoken

对于一个二进制字符串 $v$，其得分定义为：

$$\max_{0 \le i \le |v|} \left[ F(v, 1, i) \cdot F(v, i+1, |v|) \right] $$

其中 $F(v, l, r) = r - l + 1 - 2 \cdot \text{zero}(v, l, r)$，$\text{zero}(v, l, r)$ 表示 $v_l v_{l+1} \dots v_r$ 中 $0$ 的个数。如果 $l > r$，则 $F(v, l, r) = 0$。

---

题目描述

你有一个长度为 $n$ 的二进制字符串 $s$，以及一个正整数 $q$。

你会收到 $q$ 个询问。

每个询问给你一个整数 $i$（$1 \le i \le n$），你需要将 $s_i$ 翻转（$0$ 变 $1$，$1$ 变 $0$）。
对于每次修改后的字符串，你需要求出所有非空子序列的得分之和。

由于结果可能很大，输出答案对 $998244353$ 取模。

注意：修改是持久化的（即每次修改会影响后续询问）。

---

定义

• 二进制字符串：只包含字符 0 和 1 的字符串。
• 子序列：可以通过删除若干（可能为零或全部）字符得到的字符串。

---

输入

每个测试包含多个测试用例。
第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。

每个测试用例的格式如下：

• 第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 2 \cdot 10^5$，$1 \le q \le 2 \cdot 10^5$）——字符串长度和修改查询次数。
• 第二行包含长度为 $n$ 的二进制字符串 $s$。
• 接下来 $q$ 行，每行一个整数 $i$（$1 \le i \le n$），表示翻转 $s_i$。

保证所有测试用例的 $n$ 之和以及 $q$ 之和均不超过 $2 \cdot 10^5$。

---

输出

对于每个测试用例，输出 $q$ 行，每行一个整数 —— 对应每次修改后的答案（模 $998244353$）。

---

示例

输入：

3
3 2
010
1
3
10 3
0101000110
3
5
10
24 1
011001100110000101111000
24

输出：

1
5
512
768
1536
23068672

---

示例解释

第一个测试用例，第一次修改后 $s = 110$，所有非空子序列的得分之和为 $1$。
第二次修改后 $s = 111$，所有非空子序列的得分之和为 $5$。