对于二进制字符串$$$^{\text{*}}$$$ $$$v$$$, 分数 $$$v$$$ 的 被定义为最大值
$$F\big(v, 1, i\big) \cdot F\big(v, i+1, |v|\big)$$
总体 $$$i$$$ ($$$0 \leq i \leq |v|$$$)。
这里, $$$F\big(v, l, r\big) = r - l + 1 - 2 \cdot \operatorname{zero}(v, l, r)$$$,其中 $$$\operatorname{zero}(v, l, r)$$$ 表示 $$$v_lv_{l+1} 中 $$$\mathtt{0}$$$ 的数量\ldots v_r$$$。如果 $$$l \gt r$$$,则 $$$F\big(v, l, r\big) = 0$$$。
给定一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 和一个正整数 $$$q$$$。
您将被询问 $$$q$$$ 查询。
在每个查询中,都会给您一个整数 $$$i$$$ ($$$1 \leq i \leq n$$$)。您必须将 $$$s_i$$$ 从 $$$\mathtt{0}$$$ 翻转到 $$$\mathtt{1}$$$(或从 $$$\mathtt{1}$$$ 翻转到 $$$\mathtt{0}$$$)。求每次修改查询后 $$$s$$$ 的所有非空子序列$$$^{\text{†}}$$$ 的分数总和。
由于结果可能很大,因此输出对 $$$998\,244\,353$$$ 取模的答案。
请注意,修改是持久的。
$$$^{\text{*}}$$$二进制字符串是仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成的字符串。
$$$^{\text{†}}$$$二进制字符串 $$$x$$$ 是二进制字符串 $$$y$$$ 的子序列,如果 $$$x$$$ 可以通过删除几个(可能是零个或全部)字符从 $$$y$$$ 获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) - 分别是字符串 $$$s$$$ 的长度和修改查询的数量。
第二行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$,由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成。
以下 $$$q$$$ 行每行包含一个整数 $$$i$$$ ($$$1 \leq i \leq n$$$),表示 $$$s_i$$$ 从 $$$\mathtt{0}$$$ 翻转到 $$$\mathtt{1}$$$ 或从 $$$\mathtt{1}$$$ 翻转到$$$\mathtt{0}$$$。
保证所有测试用例中 $$$n$$$ 的所有值的总和以及 $$$q$$$ 的所有值的总和都不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$q$$$ 行,每行包含一个整数 - 所需的总和模 $$$998\,244\,353$$$。
示例
输入复制
33 20101310 30101000110351024 101100110011000010111100024
输出复制
1 5 512 768 1536 23068672
注意
对于第一个测试用例,第一次修改后,我们有 $$$s = \texttt{110}$$$。我们可以计算所有子序列的分数总和,如下所示:
| 指数 | 子序列 | 分数 |
| $$$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$$$ |
总结:$$$0+0+1+0+0+0+0 = 1$$$。
第二次修改后,我们有 $$$s = \texttt{111}$$$。我们可以计算所有子序列的分数总和,如下所示:
| 指数 | 子序列 | 分数 |
| $$$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$$$ |
总结:$$$0+0+1+0+1+1+2 = 5$$$。