Problem Statement

Below, a string consisting only of 0 and 1 is called a $01$ string.

For a $01$ string $x$, let $f \left( x \right)$ be the product of the number of 0s and the number of 1s contained in $x$.
Also, define $g \left( x \right)$ as follows.

• Letting $|x| = n$, it is the sum of $f \left( x' \right)$ over all of the $\frac{n \left( n+1 \right)}{2}$ contiguous substrings $x'$ of $x$.

You are given a $01$ string $S$ of length $N$. You are given $Q$ queries; process them in order.
Each query is of one of the following $2$ types.

• 1 i : Flip the $i$-th character of $S$. That is, if the $i$-th character is 0, change it to 1, and if it is 1, change it to 0. (update query)
• 2 l r : Let $S'$ be the substring of $S$ from the $l$-th character to the $r$-th character. Print $g \left( S' \right)$ modulo $998244353$. (output query)

Input

$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$ is a $01$ string of length $N$
• $1 \leq i \leq N$
• $1 \leq l \leq r \leq N$
• $N,Q,i,l,r$ are all integers
• At least $1$ output query is given

Output

Letting $M$ be the number of output queries, print $M$ lines. On the $m$-th line, print the answer to the $m$-th query among the output queries.

Sample

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