分数: 650 点
问题陈述
对于字符串 A 组成 1, 2, \dots, 9 和 B,定义 f(A) 为通过以下过程获得的字符串:
- 最初有一个空字符串 C.
- 按顺序执行以下操作 i = 1, 2, \dots, |A|:
- If A_i 是其中之一
1,2, \dots,9,追加 A_i 到年底 C. - If A_i =
B,删除最后一个字符 C。然而,如果 C 是一个空字符串,不执行任何操作。
- If A_i 是其中之一
- 让 f(A) be C 完成以上所有操作后。
给你一个字符串 S 长度 N 组成 1, 2, \dots, 9,和 B.
流程 Q 查询如下所述。每个查询属于以下两种类型之一:
- 1\ \ x\ \ c :更新 S_x to c。 (这里, c is
1,2, \dots,9,或B.) - 2\ \ l\ \ r :让 T 是通过提取形成的字符串 l-th 通过 r第一个字符 S。然后,让 U=f(T)。如果 U 为空字符串,输出 -1;否则,输出当值为 U 视为十进制整数除以 998244353.
约束
- 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 is
1,2, \dots,9,或B. - 1 \leq l \leq r \leq N
- N, Q, x, l, r 是整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{query}_i 表示 i第一个查询。
N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均以以下两种格式之一给出:
1 x c
2 l r
输出
按照问题陈述中的说明输出由换行符分隔的查询的答案。
示例输入 1
10 12 1234567891 2 5 7 2 2 8 2 1 10 1 3 B 1 4 B 2 2 4 2 2 8 2 1 10 1 7 B 2 3 9 1 3 4 2 1 10
示例输出 1
567 2345678 236323538 -1 5678 567891 589 125891
对于第一个查询, T=U= 567。因此,输出 567.
对于第三个查询, T=U= 1234567891。因此,输出 1234567891 \bmod 998244353 = 236323538.
对于第六个查询, T= 2BB 和 U 是一个空字符串。因此,输出 -1.