G - Keyboard 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 650 点

問題文

1, 2, \dots, 9 および B からなる文字列 A に対して f(A) を次の手順で得られる文字列として定義します。

  • はじめ、空文字列 C がある。
  • i = 1, 2, \dots, |A| の順に以下の操作を行う。
    • A_i が 1, 2, \dots, 9 のいずれかである場合、C の末尾に A_i を追加する。
    • A_i = B である場合、C の末尾の文字を削除する。ただし C が空文字列である場合は何もしない。
  • 上記の操作を全て終了した時点での C を f(A) とする。

1, 2, \dots, 9 および B からなる長さ N の文字列 S が与えられます。
以下で説明される Q 個のクエリを処理してください。クエリは次の 2 種類のいずれかです。

  • 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 を 10 進整数とみなした時の値を 998244353 で割った余りを出力せよ。

制約

  • 1 \leq N \leq 8 \times 10^6
  • 1 \leq Q \leq 2 \times 10^5
  • S は 1, 2, \dots, 9 および B からなる長さ N の文字列
  • 1 \leq x \leq N
  • c は 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

クエリは以下の 2 種類のいずれかの形式で与えられる。

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

1 番目のクエリについて、T=U= 567 となります。よって 567 を出力します。
3 番目のクエリについて、T=U= 1234567891 となります。よって 1234567891 \bmod 998244353 = 236323538 を出力します。
6 番目のクエリについて、T= 2BB で U は空文字列となります。よって -1 を出力します。

Score : 650 points

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.

Sample Input 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

Sample Output 1

567
2345678
236323538
-1
5678
567891
589
125891

For the first query, T=U= 567. Thus, output 567.
For the third query, T=U= 1234567891. Thus, output 1234567891 \bmod 998244353 = 236323538.
For the sixth query, T= 2BB and U is an empty string. Thus, output -1.