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` のいずれかである場合、 $ 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 $ で割った余りを出力せよ。

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{query}_i $ は $ i $ 番目のクエリを意味する。 > $ N $ $ Q $ $ S $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ クエリは以下の $ 2 $ 種類のいずれかの形式で与えられる。 > $ 1 $ $ x $ $ c $ > $ 2 $ $ l $ $ r $

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリについて、 $ T=U= $ `567` となります。よって $ 567 $ を出力します。 $ 3 $ 番目のクエリについて、 $ T=U= $ `1234567891` となります。よって $ 1234567891 \bmod 998244353 = 236323538 $ を出力します。 $ 6 $ 番目のクエリについて、 $ T= $ `2BB` で $ U $ は空文字列となります。よって $ -1 $ を出力します。 ### Constraints - $ 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 $ は整数