Range Multiplication Sum

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。$Q$ 個のクエリを順に処理してください。
$i$ 番目のクエリでは、まず整数 $T_i$ が与えられます。ここで、 $T_i$ は $1$ か $2$ のどちらかです。
次に、$T_i$ の値に応じてクエリの内容を表す入力が与えられるので、以下のように処理してください。

• $T_i=1$ のとき
  整数 $x,y$ が与えられるので、 $A_x$ を $y$ に変更してください。
• $T_i=2$ のとき
  整数 $l,r$ が与えられるので、 $\sum_{i=l}^{r-1} \sum_{j=i+1}^{r} (A_i×A_j)$ を $998244353$ で割った余りを出力してください。

制約

• $2\leq N \leq 200000$
• $1\leq Q \leq 200000$
• $0\leq A_i \leq 998244352$
• $T_i=1$ または $T_i=2$
• $1\leq x \leq N$
• $0\leq y \leq 998244352$
• $1 \leq l < r \leq N$
• 入力は全て整数 　　

入力

入力は以下の形式で標準入力から与えられます。

$3$ 行目から $Q+2$ 行目の $Query_i$ は以下のいずれかです。

出力

$T_i=2$ の各クエリについて、改行区切りで答えを出力してください。

入力例1

6 4
4 1 8 2 6 9
2 2 4
2 4 6
1 6 0
2 4 6

出力例1

26
84
12

$1$ 番目のクエリは $\sum_{i=2}^{3} \sum_{j=i+1}^{4} (A_i×A_j)$ を出力せよというものです。$(1×8)+(1×2)+(8×2)=8+2+16=26$ なので、$26$ と出力します。

$2$ 番目のクエリは $\sum_{i=4}^{5} \sum_{j=i+1}^{6} (A_i×A_j)$ を出力せよというものです。$(2×6)+(2×9)+(6×9)=12+18+54=84$ なので、$84$ と出力します。

$3$ 番目のクエリは $A_6$ を $0$ に変更せよというものです。 $A=(4,1,8,2,6,0)$ となります。

$4$ 番目のクエリは $\sum_{i=4}^{5} \sum_{j=i+1}^{6} (A_i×A_j)$ を出力せよというものです。$(2×6)+(2×0)+(6×0)=12+0+0=12$ なので、$12$ と出力します。

入力例2

2 1
998244352 998244352
2 1 2

出力例2

1

$998244352×998244352=996491786299899904$ ですが、 $998244353$ で割った余りを出力する必要があることに注意してください。