問題文
だれさんは結合法則が嫌いです。ある日、だれさんは次のような関数 f を見つけました。
f(a,b)=2a+b mod998244353 (a,b∈Z≥0)
この関数は一般に f(f(a,b),c)=f(a,f(b,c)) となるので、結合法則を満たしません。
だれさんはこの関数を非常に気に入ったため、この関数を使って以下のような問題を考えました。解いてください。
長さ N の整数列 A1,A2,…,AN が与えられます。Q 個のクエリが与えられるので処理してください。
- 0 i x Ai=x と変更する。
- 1 l r f(⋯f(f(Al,Al+1),Al+2),⋯,Ar) を出力する。
ただし 2a+b mod998244353 で a+b≡2z mod998244353, 0≤z<998244353 を満たす唯一の整数 z を表します。
入力
入力は以下の形式で与えられる。
各クエリは以下のいずれかの形式で与えられる。
制約
- 2≤N≤2×105
- 1≤Q≤2×105
- 0≤Ai<998244353
- type0のクエリにおいて、1≤i≤N, 0≤x<998244353
- type1のクエリにおいて、1≤l<r≤N (特に l=r であることに注意せよ。)
サンプル
サンプル1
4 3
4 8 4 4
1 2 3
0 1 8
1 1 4
クエリ 1 では 28+4=6 、クエリ 3 では 2228+8+4+4=5 となります。
サンプル2
10 10
133403202 48156701 430605633 221185434 63259974 744846636 519917398 555439784 822174706 352853132
1 5 6
1 2 7
0 1 480330587
0 1 618069247
1 3 6
0 10 77287957
1 1 4
1 3 8
0 8 536865211
1 3 8
出力2
404053305
170911907
594492739
551083457
306761338
796596228