O - 最大区間和 解説 /

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

問題文

長さ N の数列 A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N) が与えられます。

今から Q 個のクエリが与えられるので、順に処理してください。 それぞれのクエリは以下のいずれかの形式で与えられます：

  • 1 p x : A_p を x に変更する。
  • 2 p x : B_p を x に変更する。
  • 3 l r x : l\leq i\leq j\leq r かつ A_i+A_{i+1}+\dots+A_j\equiv x \pmod 3 を満たすような整数の組 (i,j) が存在するか判定し、 存在するならばそのような (i,j) における B_i+B_{i+1}+\dots+B_j の最大値を出力する。

制約

  • 1\leq N,Q \leq 2\times 10^5
  • 0\leq A_i \leq 2
  • -10^9\leq B_i \leq 10^9
  • 1 種類目のクエリについて、
    • 1\leq p \leq N
    • 0\leq x \leq 2
  • 2 種類目のクエリについて、
    • 1\leq p \leq N
    • -10^9\leq x \leq 10^9
  • 3 種類目のクエリについて、
    • 1\leq l\leq r \leq N
    • 0\leq x \leq 2
  • 入力は全て整数

入力

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

N Q
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q

ここで、\mathrm{Query}_k\ (1\leq k\leq Q) は k 個目のクエリを表し、以下のいずれかである：

1 p x

2 p x

3 l r x

出力

3 種類目のクエリの個数を c として、c 行出力せよ。 k\ (1\leq k \leq c) 行目には、3 種類目のクエリのうち k 個目のものにおいて、条件を満たす整数の組 (i,j) が存在するならばそのような (i,j) における B_i+B_{i+1}+\dots+B_j の最大値を、存在しないならば No を出力せよ。

入力例 1

3 5
0 1 2
3 12 -5
3 1 3 0
1 3 0
3 2 3 1
2 3 2
3 2 3 1

出力例 1

10
12
14
  • 1 個目のクエリ：1\leq i\leq j\leq 3 かつ A_i+A_{i+1}+\dots+A_j\equiv 0 \pmod 3 を満たす整数の組 (i,j) は (1,1),(1,3),(2,3) の 3 つである。 B_i+B_{i+1}+\dots+B_j の値はそれぞれ 3,10,7 なので、最大値である 10 を出力する。
  • 2 個目のクエリ：A_3 を 0 に変更する。
  • 3 個目のクエリ：2\leq i\leq j\leq 3 かつ A_i+A_{i+1}+\dots+A_j\equiv 1 \pmod 3 を満たす整数の組 (i,j) は (2,2),(2,3) の 2 つである。 B_i+B_{i+1}+\dots+B_j の値はそれぞれ 12,7 なので、最大値である 12 を出力する。
  • 4 個目のクエリ：B_3 を 2 に変更する。
  • 5 個目のクエリ：2\leq i\leq j\leq 3 かつ A_i+A_{i+1}+\dots+A_j\equiv 1 \pmod 3 を満たす整数の組 (i,j) は (2,2),(2,3) の 2 つである。 B_i+B_{i+1}+\dots+B_j の値はそれぞれ 12,14 なので、最大値である 14 を出力する。

入力例 2

1 3
2
100
3 1 1 0
3 1 1 1
3 1 1 2

出力例 2

No
No
100

1 個目のクエリについて、1\leq i\leq j\leq 1 かつ A_i+A_{i+1}+\dots+A_j\equiv 0 \pmod 3 を満たす整数の組 (i,j) は存在しません。

入力例 3

1 1
2
100
1 1 0

出力例 3



3 種類目のクエリが一つもないこともあります。













入力例 4
10 10
1 1 2 0 0 2 0 2 0 0
-52 -52 14 -11 -2 -54 46 8 26 -17
3 1 9 2
2 8 71
1 10 1
2 9 86
1 5 2
3 7 7 0
3 4 5 0
2 10 100
2 1 -95
1 1 1












出力例 4
80
46
-11












Problem Statement
You are given two sequences A=(A_1,\ldots,A_N) and B=(B_1,\ldots,B_N) of length N.


Process the given Q queries in order.
Each query is of one of the following kinds:


    

  • 1 p x: set A_p to x.
    • 

  • 2 p x: set B_p to x.
    • 

  • 3 l r x: determine if there exists an integer pair (i,j) such that l\leq i\leq j\leq r and A_i+A_{i+1}+\dots+A_j\equiv x \pmod 3.
If it exists, print the maximum value of B_i+B_{i+1}+\dots+B_j among such (i,j).
    • 












Constraints
    

  • 1\leq N,Q \leq 2\times 10^5
    • 

  • 0\leq A_i \leq 2
    • 

  • -10^9\leq B_i \leq 10^9
    • 

  • For every query of the first kind:
      

    • 1\leq p \leq N
      • 

    • 0\leq x \leq 2
      • 

    

    • 

  • For every query of the second kind:
      

    • 1\leq p \leq N
      • 

    • -10^9\leq x \leq 10^9
      • 

    

    • 

  • For every query of the third kind:
      

    • 1\leq l\leq r \leq N
      • 

    • 0\leq x \leq 2
      • 

    

    • 

  • All input values are integers.
    • 
















Input
The input is given from Standard Input in the following format:


N Q
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q



Here, \mathrm{Query}_k\ (1\leq k\leq Q) denotes the k-th query in one of the following format:


1 p x



2 p x



3 l r x












Output
Print c lines, where c is the number of queries of the third kind.
The k-th line (1\leq k \leq c) should respond to k-th query of the third kind, containing the maximum value of B_i+B_{i+1}+\dots+B_j among the conforming pairs (i,j) if such a pair exists, or No otherwise.















Sample Input 1
3 5
0 1 2
3 12 -5
3 1 3 0
1 3 0
3 2 3 1
2 3 2
3 2 3 1












Sample Output 1
10
12
14



    

  • 1-st query: there are three integer pairs (i,j) such that 1\leq i\leq j\leq 3 and A_i+A_{i+1}+\dots+A_j\equiv 0 \pmod 3: namely (1,1),(1,3), and (2,3).
  The values of B_i+B_{i+1}+\dots+B_j are 3,10, and 7, respectively, so print the maximum value 10 among them.
    • 

  • 2-nd query: set A_3 to 0.
    • 

  • 3-rd query: there are two integer pairs (i,j) such that 2\leq i\leq j\leq 3 and A_i+A_{i+1}+\dots+A_j\equiv 1 \pmod 3: namely (2,2) and (2,3).
  The values of B_i+B_{i+1}+\dots+B_j are 12 and 7, respectively, so print the maximum value 12 among them.
    • 

  • 4-th query: set B_3 to 2.
    • 

  • 5-th query: there are two integer pairs (i,j) such that 2\leq i\leq j\leq 3 and A_i+A_{i+1}+\dots+A_j\equiv 1 \pmod 3: namely (2,2) and (2,3).
  The values of B_i+B_{i+1}+\dots+B_j are 12 and 14, respectively, so print the maximum value 14 among them.
    • 














Sample Input 2
1 3
2
100
3 1 1 0
3 1 1 1
3 1 1 2












Sample Output 2
No
No
100



For the 1-st query, there is no integer pair (i,j) such that 1\leq i\leq j\leq 1 and A_i+A_{i+1}+\dots+A_j\equiv 0 \pmod 3.













Sample Input 3
1 1
2
100
1 1 0












Sample Output 3


There may be no query of the third type.













Sample Input 4
10 10
1 1 2 0 0 2 0 2 0 0
-52 -52 14 -11 -2 -54 46 8 26 -17
3 1 9 2
2 8 71
1 10 1
2 9 86
1 5 2
3 7 7 0
3 4 5 0
2 10 100
2 1 -95
1 1 1












Sample Output 4
80
46
-11