問題文

 長さ NN の数列 (A1,A2,,AN)(A_1,A_2,\ldots,A_N) が与えられます.

 QQ 個のクエリが与えられるので,順番に全て処理して下さい. qq 番目 (1qQ)(1 \leq q \leq Q) のクエリは以下の 33 つのいずれかの形式で,それぞれ次のようなクエリを表します.

1 xq yq :1 ~ x_q ~ y_q ~ : AxqA_{x_q}yqy_q を足す.
2 yq :2 ~ y_q ~ : i=1,2,,Ni=1,2,\ldots,N について AiA_iyqy_q を足す.
3 xq :3 ~ x_q ~ : AxqA_{x_q} を出力する.

制約

1N2×1051 \leq N \leq 2×10^5
1Q2×1051 \leq Q \leq 2×10^5
1xqN1 \leq x_q \leq N
0yq1090 \leq y_q \leq 10^9

入力

・入力は全て整数である.

N Q
A1 A2 ... AN
query1
query2
...
queryQ

queryi (i=1,2,,Q)\mathrm{query}_i ~ (i=1,2,\ldots,Q)ii 番目のクエリを表す.

出力

(クエリ 33 の個数)行出力して下さい.

サンプル

入力1
4 3
1 2 3 4
2 1
1 1 3
3 2
出力1
3

(1,2,3,4)(2,3,4,5)(5,3,4,5)(1,2,3,4)→(2,3,4,5)→(5,3,4,5) と変化し,33 を出力します.

入力2
5 5
5 3 4 2 1
1 2 500
2 100
1 3 50
3 3
3 1
出力2
154
105

提出


Go (1.21)