시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB17000.000%

문제

Today, Esmaan decided to prove to the world that he is not ordinary. He went to take the exam to become a data structures master. But the first question of the exam stumped him. Help him solve the problem:

You have a sequence of integers $a_1, a_2, \ldots, a_n$. In addition, you have three empty sequences: $A$, $B$, and $C$.

  • Let $f(\ell, r)$ be the maximum among the numbers $a_{\ell}, a_{\ell + 1}, \ldots, a_r$.
  • Let $g(p_1, p_2, p_3)$ be $f(\min(p_1, p_2, p_3), \max(p_1, p_2, p_3))$.
  • Let $S$ be the sum of the values $g(A_i, B_j, C_k)$ for all possible combinations $(i, j, k)$ where $1 \le i \le \mathrm{size}(A)$, $1 \le j \le \mathrm size(B)$, and $1 \le k \le \mathrm{size}(C)$.

You need to perform $q$ queries of the following type:

  • "$X$ $\mathit{val}$": add the value $\mathit{val}$ to the end of sequence $X$.

After each query, output $S$ modulo $998\,244\,353$.

입력

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 10^5$): the number of elements in the sequence and the number of queries.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^5$): the elements of the sequence.

Then follow $q$ lines, each containing a query in the format "$X$ $\mathit{val}$" ($X \in \{$A, B, C$\}$, $1 \le \mathit{val} \le n$).

출력

After each query, output a line with a single integer: the current value of $S$ modulo $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