Majorant

다중집합의 majorant는 다른 모든 원소를 합친 것보다 더 많이 등장하는 원소이다. majorant가 없는 다중집합도 있다.

양의 정수 $n$개로 이루어진 배열 $a_1, a_2, \ldots, a_n$이 주어진다. 배열 $a$의 부분 배열은 $1 \le l \le r \le n$을 만족하는 $a_l, a_{l+1}, \ldots, a_r$이다.

질의는 $m$개이며, 두 종류가 있다.

1. Update p q: $a_p$의 값을 $q$로 바꾼다.
2. Query p q ($p \le q$): $b_1 = a_p, b_2 = a_{p+1}, \ldots, b_{q-p+1} = a_q$라 하자. $b$의 부분 배열 중 $i$가 majorant인 부분 배열의 개수에 $i$를 곱한 값을 구한다. 이 값을 $b$의 어떤 부분 배열이든 majorant로 갖는 서로 다른 모든 $i$에 대해 더하고, 그 합을 998244353으로 나눈 나머지를 구한다.

첫 줄에 $n$이 주어진다. 둘째 줄에 배열의 원소 $n$개가 주어진다. 셋째 줄에 $m$이 주어진다. 이어서 $m$개의 줄에 암호화된 질의를 나타내는 정수 $l$, $r$, $t$가 하나씩 주어진다.

last_output은 프로그램이 표준 출력에 마지막으로 출력한 수이다. 아직 출력한 수가 없으면 0으로 한다.

$type = ((t + last\_output) \bmod 2) + 1$을 계산한다.

$type = 1$이면 Update 질의이며, $p = ((l + last\_output) \bmod n) + 1$, $q = ((r + last\_output) \bmod 100000000) + 1$이다.

$type = 2$이면 Query 질의이며, $p = ((l + last\_output) \bmod n) + 1$, $q = ((r + last\_output) \bmod n) + 1$이다.

type이 2인 질의마다 답을 한 줄에 하나씩 출력한다.

• $1 \le n \le 200000$
• 배열 $a$의 모든 원소 $x$는 $1 \le x \le 100000000$을 만족한다.
• $1 \le m \le 100$
• $1 \le l, r, t \le 100000000$

복호화하면 첫 번째 질의는 query, p=1, q=4가 된다. majorant가 1인 부분 배열은 2개, majorant가 2인 부분 배열은 5개이므로 답은 $2 \cdot 1 + 5 \cdot 2 = 12$이다.

두 번째 질의는 update, p=3, q=3이 된다. 이후 배열은 1, 2, 3, 1이 된다.

세 번째 질의는 query, p=1, q=3이다. majorant가 1인 부분 배열은 1개, 2인 부분 배열은 1개, 3인 부분 배열은 1개 있다.