AT_aalc001_e RGB

You are given a sequence of nonnegative integers $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ and a string $ S $ of length $ N $ consisting of `R`, `G`, and `B`. Let $ S_i $ denote the $ i $ -th character of $ S $ . Process $ Q $ queries. Each query is of one of the following $ 2 $ types: - `1 i x`: Change $ A_i $ to $ x $ . - `2 l r`: Print the sum of $ A_iA_jA_k $ over all triples of integers $ (i,j,k) $ such that $ l\leq i\lt j\lt k\leq r $ and $ S_i,S_j,S_k $ are `R`, `G`, `B` in this order, modulo $ 998244353 $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ S $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is given in one of the following formats: > $ 1 $ $ i $ $ x $ > $ 2 $ $ l $ $ r $

Let $ q $ be the number of type $ 2 $ queries. Print $ q $ lines. The $ j $ -th line should contain the answer to the $ j $ -th type $ 2 $ query.

### Sample Explanation 1 For the first query, the $ 3 $ triples satisfying the conditions are $ (1,2,3),(1,2,5),(1,4,5) $ . The sum of their products is $ 1\times2\times3+1\times2\times5+1\times4\times5=36 $ . ### Constraints - $ 1\leq N\leq 2\times 10^5 $ - $ 1\leq Q\leq 2\times 10^5 $ - $ 0\leq A_i\leq 10^9 $ - $ S $ is a string of length $ N $ consisting of `R`, `G`, and `B`. - For type $ 1 $ queries, $ 1\leq i\leq N $ , $ 0\leq x\leq 10^9 $ - For type $ 2 $ queries, $ 1\leq l\leq r\leq N $ - All numerical values in the input are integers.