問題文


 長さ の数列 が与えられます.

  個のクエリが与えられるので,順番に全て処理して下さい. 番目 のクエリは以下の つのいずれかの形式で,それぞれ次のようなクエリを表します.

を足す.
について を足す.
を出力する.

制約





入力


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

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

番目のクエリを表す.

出力


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

サンプル


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

と変化し, を出力します.

入力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.14)