Alternating Sum

整数を要素とする長さ n の配列と、合計 q 回のクエリが与えられています。クエリには2種類があり、特定のインデックス p にある要素の値を更新するものと、区間 [l; r] に対して交互和 (alternating sum) を計算するものです。

区間 [l; r] の交互和は、「その区間内でインデックスが偶数の要素の合計」から「インデックスが奇数の要素の合計」を引いた値として定義されます。具体的には、もし部分配列 [l; r] の要素が [ $$a_l, a_{l+1}, \dots, a_r$$ ] であるとき、交互和は

入力

1 行目に、配列のサイズを表す整数 n とクエリの総数を表す整数 q が与えられます (1 ≤ n, q ≤ )。
2 行目には、配列の要素を表す n 個の整数 が空白区切りで与えられます ()。
続く q 行にはクエリが与えられ、形式は 1 l r または 2 p x のいずれかです。ここで、1 は区間 [l; r] の交互和を求めるクエリ、2 はインデックス p を値 x に更新するクエリを表します (1 ≤ p ≤ n, 1 ≤ x ≤ , 1 ≤ l ≤ r ≤ n)。

出力

クエリが種類 2 の場合ごとに、その交互和を1行ずつ出力してください。

例