Data Structures Master

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$.