今天，Esmaan 决定向世界证明他并非凡人。他去参加了一场成为数据结构大师的考试。但考试的第一道题就把他难住了。请帮他解决这个问题：

你有一个整数序列 $a_1, a_2, \dots, a_n$。此外，你还有三个空序列：$A$、$B$ 和 $C$。

• 令 $f(\ell, r)$ 为数字 $a_\ell, a_{\ell+1}, \dots, a_r$ 中的最大值。
• 令 $g(p_1, p_2, p_3)$ 为 $f(\min(p_1, p_2, p_3), \max(p_1, p_2, p_3))$。
• 令 $S$ 为所有满足 $1 \le i \le \text{size}(A)$，$1 \le j \le \text{size}(B)$ 以及 $1 \le k \le \text{size}(C)$ 的组合 $(i, j, k)$ 的 $g(A_i, B_j, C_k)$ 之和。

你需要执行 $q$ 次以下类型的查询：

• “$X \ val$”：将值 $val$ 添加到序列 $X$ 的末尾。

每次查询后，输出 $S \pmod{998\,244\,353}$。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)：序列中的元素个数和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$)：序列的元素。

接下来 $q$ 行，每行包含一个格式为 “$X \ val$” 的查询 ($X \in \{A, B, C\}, 1 \le val \le n$)。

输出格式

每次查询后，输出一行，包含一个整数：当前的 $S \pmod{998\,244\,353}$ 的值。

样例

样例输入 1

5 5
2 2 9 1 10
A 5
A 1
C 4
B 1
C 5

样例输出 1

0
0
0
19
39

样例输入 2

10 10
5 6 5 5 10 4 8 9 5 4
C 8
C 8
B 8
B 2
A 7
C 7
C 4
B 4
A 7
B 5

样例输出 2

0
0
0
0
38
57
77
117
234
314