Problem Statement

For a string $A$ consisting of 1, 2, $\dots$, 9 and B, define $f(A)$ as the string obtained by the following procedure:

• Initially, there is an empty string $C$.
• Perform the following operations in the order $i = 1, 2, \dots, |A|$:
• If $A_i$ is one of 1, 2, $\dots$, 9, append $A_i$ to the end of $C$.
  • If $A_i =$ B, delete the last character of $C$. However, if $C$ is an empty string, do nothing.
• Let $f(A)$ be $C$ after completing all the above operations.

You are given a string $S$ of length $N$ consisting of 1, 2, $\dots$, 9, and B. Process $Q$ queries described below. Each query is of one of the following two types:

• $1\ \ x\ \ c$ : Update $S_x$ to $c$. (Here, $c$ is 1, 2, $\dots$, 9, or B.)
• $2\ \ l\ \ r$ : Let $T$ be the string formed by extracting the $l$-th through $r$-th characters of $S$. Then, let $U=f(T)$. If $U$ is an empty string, output $-1$; otherwise, output the remainder when the value of $U$ regarded as a decimal integer is divided by $998244353$.

Constraints

• $1 \leq N \leq 8 \times 10^6$
• $1 \leq Q \leq 2 \times 10^5$
• $S$ is a string of length $N$ consisting of 1, 2, $\dots$, 9, and B.
• $1 \leq x \leq N$
• $c$ is 1, 2, $\dots$, 9, or B.
• $1 \leq l \leq r \leq N$
• $N, Q, x, l, r$ are integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{query}_i$ denotes the $i$-th query.

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following two formats:

1 x c

2 l r

Output

Output the answers to the queries separated by newlines, following the instructions in the problem statement.