AT_abc434_g.[ABC434G] Keyboard

对于一个只包含 1、2、$\dots$、9 和 B 的字符串 $A$，定义 $f(A)$ 为通过以下过程得到的字符串：

• 初始有一个空字符串 $C$。
• 依次对 $i = 1, 2, \dots, |A|$ 进行如下操作：
  • 如果 $A_i$ 是 1、2、$\dots$、9，则将 $A_i$ 加到 $C$ 的末尾。
  • 如果 $A_i = \text{B}$，则删除 $C$ 的最后一个字符。如果 $C$ 为空则不进行操作。
• 完成所有操作后，将 $C$ 作为 $f(A)$。

给定一个长度为 $N$ 的字符串 $S$，由 1、2、$\dots$、9 和 B 组成。现在要处理 $Q$ 个如下描述的查询，每个查询有两种类型：

• $1\ x\ c$ ：将 $S_x$ 更新为 $c$。($c$ 为 1、2、$\dots$、9 或 B)
• $2\ l\ r$ ：取 $S$ 的第 $l$ 到第 $r$ 个字符组成字符串 $T$，令 $U=f(T)$。如果 $U$ 为空串，输出 $-1$；否则，将 $U$ 视为十进制整数后对 $998244353$ 取余，输出结果。

输入通过标准输入给出，格式如下，其中 $\mathrm{query}_i$ 表示第 $i$ 个查询：

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

每个查询格式如下两种之一：

$1\ x\ c$

$2\ l\ r$

对于每个查询类型为 $2$ 的操作，按照题面要求用换行分隔依次输出答案。

样例解释 1

对于第一个查询，$T=U=567$，输出 $567$。
对于第三个查询，$T=U=1234567891$，输出 $1234567891 \bmod 998244353 = 236323538$。
对于第六个查询，$T=2BB$，$U$ 为空串，输出 $-1$。

约束条件

• $1 \leq N \leq 8 \times 10^6$
• $1 \leq Q \leq 2 \times 10^5$
• $S$ 为长度为 $N$ 的字符串，仅包含 1、2、$\dots$、9 和 B
• $1 \leq x \leq N$
• $c$ 为 1、2、$\dots$、9 或 B
• $1 \leq l \leq r \leq N$
• $N, Q, x, l, r$ 都为整数。

由 ChatGPT 5 翻译