AT_abc434_g [ABC434G] Keyboard

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 $ .

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 the answers to the queries separated by newlines, following the instructions in the problem statement.

### Sample Explanation 1 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 $ . ### 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.