자료구조 마스터

오늘 에스마안은 자신이 평범하지 않다는 것을 세상에 증명하기로 했다. 그는 자료구조 마스터가 되기 위한 시험을 보러 갔다. 그런데 시험의 첫 문제에서 막히고 말았다. 이 문제를 풀도록 도와주자.

정수 수열 $a_1, a_2, \ldots, a_n$이 주어진다. 또한 비어 있는 수열 $A$, $B$, $C$가 세 개 있다.

• $f(\ell, r)$은 $a_{\ell}, a_{\ell + 1}, \ldots, 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$는 가능한 모든 $(i, j, k)$ 조합에 대해 $g(A_i, B_j, C_k)$를 더한 값이다. 여기서 $1 \le i \le \mathrm{size}(A)$, $1 \le j \le \mathrm{size}(B)$, $1 \le k \le \mathrm{size}(C)$이다.

다음 형식의 질의를 $q$개 처리해야 한다.

• X val: 수열 $X$의 끝에 $val$을 추가한다.

각 질의를 처리한 뒤 $S$를 $998244353$으로 나눈 나머지를 출력한다.

첫째 줄에 두 정수 $n$과 $q$ ($1 \le n, q \le 10^5$)가 주어진다. 둘째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^5$)이 주어진다. 이후 $q$개의 줄에 X val 형식의 질의가 주어진다. 여기서 $X$는 A, B, C 중 하나이고, $1 \le val \le n$이다.

각 질의를 처리한 직후의 $S$를 $998244353$으로 나눈 나머지를 한 줄에 출력한다.