問題文

長さ $N$ の数列 $A$ と $B$ があります。$A$ は入力で与えられる数列であり、$B$ は最初すべての要素が $0$ である数列です。
以下の $2$ 種類のクエリが合計で $Q$ 個与えられるので、それらを順にすべて処理したあとの数列 $B$ を求めてください。

• A $x$ $y$ : $A_x$ に $y$ を足す
• B $x$ $y$ : $x\leq i\leq y$ をみたす整数 $i$ について、$B_i$ に $A_i$ を足す

入力

$N\ Q$
$A_1\ A_2\ \cdots \ A_N$
$c_1\ x_1\ y_1$
$c_2\ x_2\ y_2$
$\vdots$
$c_Q\ x_Q\ y_Q$

• 与えられる数はすべて整数
• $1\leq N, Q\leq 200000$
• $1\leq A_i \leq 10^9$
• $c_i$ は 'A', 'B' のいずれか
• $c_i$ が 'A' のとき、$1\leq x_i \leq N$, $1\leq y_i \leq 100000$
• $c_i$ が 'B' のとき、$1\leq x_i \leq y_i \leq N$

出力

すべてのクエリを処理した後の数列 $B$ の各要素を順に空白区切りで出力してください。 最後に改行してください。

サンプル

7 3
9 8 1 9 6 10 8
B 2 5
A 7 9
B 4 7

0 8 1 18 12 10 17

10 10
1 4 1 5 9 2 6 5 3 5
A 2 7
A 5 9
B 1 4
B 6 10
A 10 3
B 1 2
A 8 3
B 4 9
A 6 2
B 1 10

3 33 2 15 36 8 18 21 9 13