区間和クエリ 2

n 個の要素からなる配列と q 個のクエリが与えられています。クエリには、以下の 2 種類があります。

1. 指定された区間の要素の合計を求める

2. 指定された位置の配列要素を更新する

これらのクエリを効率的に処理することが求められます。

入力

最初の行には、配列の要素数を表す整数 n と、クエリの数を表す整数 q (1 ≤ n, q ≤ 100000) が与えられます。

次の行には、空白区切りで n 個の整数 a_1, a_2, ..., a_n (−10^9 ≤ ai ≤ 10^9) が与えられます。これは配列の初期状態を表します。

続く q 行には、それぞれクエリが 1 行ずつ与えられます:

1. 区間和クエリの場合: 行の先頭が 1 で、続けて li と ri (1 ≤ li ≤ ri ≤ n) が与えられます。指定された範囲 [l_i, r_i] の要素の合計を求めます。

2. 配列の更新クエリの場合: 行の先頭が 2 で、続けて pi と xi (1 ≤ pi ≤ n, −10^9 ≤ xi ≤ 10^9) が与えられます。これは配列の pi 番目の要素を新しい値 xi に更新する操作です。

出力

区間和クエリごとに、指定された範囲の要素の合計を 1 行につき 1 つずつ出力してください。

例