E - RGB 解説 /

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

配点 : 3 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) と、R, G, B からなる長さ N の文字列 S が与えられます。S の i 文字目を S_i とします。

クエリを Q 個処理してください。クエリは以下の 2 種類のいずれかです。

  • 1 i x：A_i を x に変更する。
  • 2 l r：l\leq i\lt j\lt k\leq r かつ S_i,S_j,S_k がこの順に R, G, B である整数の組 (i,j,k) すべてに対する A_iA_jA_k の総和を 998244353 で割った余りを出力する。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq Q\leq 2\times 10^5
  • 0\leq A_i\leq 10^9
  • S は R, G, B からなる長さ N の文字列
  • 1 種類目のクエリについて、1\leq i\leq N, 0\leq x\leq 10^9
  • 2 種類目のクエリについて、1\leq l\leq r\leq N
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \ldots A_N
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

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

1 i x

2 l r

出力

2 種類目のクエリの個数を q として、q 行出力せよ。j 行目には、j 番目の 2 種類目のクエリに対する答えを出力せよ。

入力例 1

5 5
1 2 3 4 5
RGBGB
2 1 5
1 2 10
2 1 5
2 2 4
2 1 3

出力例 1

36
100
0
30

最初のクエリについて、条件を満たす組は (1,2,3),(1,2,5),(1,4,5) の 3 つです。これらに対する積の総和は 1\times2\times3+1\times2\times5+1\times4\times5=36 です。

入力例 2

3 5
1000000000 1000000000 1000000000
RGB
2 1 3
1 2 998244353
2 1 3
1 2 998244354
2 1 3

出力例 2

747068572
0
716070898

Score: 3 points

Problem Statement

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.

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.

Input

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

Output

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

5 5
1 2 3 4 5
RGBGB
2 1 5
1 2 10
2 1 5
2 2 4
2 1 3

Sample Output 1

36
100
0
30

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.

Sample Input 2

3 5
1000000000 1000000000 1000000000
RGB
2 1 3
1 2 998244353
2 1 3
1 2 998244354
2 1 3

Sample Output 2

747068572
0
716070898