問題文
長さ N の数列 (A1,A2,…,AN) が与えられます.
Q 個のクエリが与えられるので,順番に全て処理して下さい.
q 番目 (1≤q≤Q) のクエリは以下の
3 つのいずれかの形式で,それぞれ次のようなクエリを表します.
・1 xq yq : Axq に yq を足す.
・2 yq : i=1,2,…,N について Ai に yq を足す.
・3 xq : Axq を出力する.
制約
・1≤N≤2×105
・1≤Q≤2×105
・1≤xq≤N
・0≤yq≤109
入力
・入力は全て整数である.
N Q
A1 A2 ... AN
query1
query2
...
queryQ
queryi (i=1,2,…,Q) は i 番目のクエリを表す.
出力
(クエリ 3 の個数)行出力して下さい.
サンプル
入力1
4 3
1 2 3 4
2 1
1 1 3
3 2
(1,2,3,4)→(2,3,4,5)→(5,3,4,5) と変化し,3 を出力します.
入力2
5 5
5 3 4 2 1
1 2 500
2 100
1 3 50
3 3
3 1