给定一个整数 $$$n$$$ 和一个 $$$n-1$$$ 整数的序列 $$$a$$$,每个元素要么是 $$$0$$$ 要么是 $$$1$$$。
您需要构建一个长度为 $$$n$$$ 的字符串,使得:
- 每个字母都是“abcd”之一;
- 如果 $$$a_i=1$$$,则字符串的第 $$$i$$$ 个后缀按字典顺序小于第 $$$(i+1)$$$ 个后缀;
- 如果 $$$a_i=0$$$,则字符串的第 $$$i$$$ 个后缀按字典顺序大于第 $$$(i+1)$$$ 个后缀。
您将被询问 $$$q$$$ 形式的查询:
- $$$i$$$ ($$$1 \le i \le n - 1$$$) — 翻转 $$$a_i$$$ 的值(如果 $$$a_i=0$$$,则将 $$$a_i$$$ 设置为 $$$1$$$,反之亦然)。
在每个查询后打印满足给定约束模 $$$998\,244\,353$$$ 的不同字符串的数量。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 10^5$$$; $$$1 \le q \le 10^5$$$) - 字符串的长度和查询的数量。
第二行包含 $$$n-1$$$ 整数 $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$a_i \in \{0, 1\}$$$) - 对字符串后缀的约束。
接下来的 $$$q$$$ 行都包含一个查询:一个整数 $$$i$$$ ($$$1 \le i \le n - 1$$$) — 翻转 $$$a_i$$$ 的值(如果 $$$a_i=0$$$,则将 $$$a_i$$$ 设置为 $$$1$$$,反之亦然)。
输出
在每个查询后打印满足给定约束模 $$$998\,244\,353$$$ 的不同字符串的数量。
示例
输入 #1
2 2 0 1 1
输出 #1
6 10
输入 #2
3 4 0 0 1 2 1 2
输出 #2
20 10 14 20
输入 #3
10 10 0 0 0 1 1 1 0 1 0 4 1 8 4 2 9 5 6 6 8
输出 #3
1815 3201 2710 2776 2290 1644 2668 1271 2668 2436
注意
字符串的第 $$$i$$$ 后缀是从第 $$$i$$$ 个位置开始到最后一个位置结束的连续子字符串。
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。
如果存在 $$$i$$$ 位置使得 $$$a_i \neq b_i$$$,则长度为 $$$n$$$ 的两个字符串 $$$a$$$ 和 $$$b$$$ 会有所不同。