問題文

以下では、 0 と 1 のみからなる文字列を $01$ 列と呼びます。

$01$ 列 $x$ に対し、 $f \left( x \right)$ を $x$ が含む 0 の数と 1 の数の積とします。
また $g \left( x \right)$ を以下のように定めます。

• $|x| = n$ として $\frac{n \left( n+1 \right)}{2}$ 通りある $x$ の連続部分文字列 $x'$ 全てについて、 $f \left( x' \right)$ を足し合わせた値。

長さ $N$ の $01$ 列 $S$ が与えられます。 $Q$ 個のクエリが与えられるので、順に処理してください。
クエリは次の $2$ 種類のいずれかです。

• 1 i : $S$ の $i$ 文字目を入れ替える。すなわち $i$ 文字目が 0 なら 1 に、 1 なら 0 にする。(変更クエリ)
• 2 l r : $S$ の $l$ 文字目から $r$ 文字目までの部分文字列を $S'$ とする。 $g \left( S' \right)$ を $998244353$ で割った余りを出力する。(出力クエリ)

入力

$N\ \ Q$
$S$
$\mathrm{query}1$
$\mathrm{query}2$
$\vdots$
$\mathrm{query}Q$

1 i

2 l r

• $1 \leq N,Q \leq 1.5 \times 10^5$
• $S$ は長さ $N$ の $01$ 列
• $1 \leq i \leq N$
• $1 \leq l \leq r \leq N$
• $N,Q,i,l,r$ は全て整数
• 出力クエリは $1$ 個以上与えられる

出力

出力クエリが $M$ 個あるとして $M$ 行出力してください。 $m$ 行目には出力クエリの中で $m$ 番目のクエリに対応する答えを出力してください。

サンプル

6 6
010110
2 1 3
1 3
2 4 5
1 5
2 4 5
2 1 1

4
0
1
0

1 5
0
1 1
2 1 1
2 1 1
1 1
2 1 1

0
0
0

38 17
00011111001010001001101100101011101110
2 12 19
1 8
2 25 36
1 19
2 1 11
2 1 3
2 6 33
2 14 21
1 8
2 7 12
2 5 36
2 29 35
2 17 18
1 16
1 9
2 11 25
1 27

100
529
387
0
14391
112
43
24138
64
1
1236