問題文

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

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

入力

$NQ$
$A_1{A}_2\cdots A_N$
$c_1{x}_1{y}_1$
$c_2{x}_2{y}_2$
$⋮$
$c_Q{x}_Q{y}_Q$

• 与えられる数はすべて整数
• $1\le N,Q\le 200000$
• $1\le A_i\le {10}^9$
• $c_i$ は 'A', 'B' のいずれか
• $c_i$ が 'A' のとき、$1\le x_i\le N$, $1\le y_i\le 100000$
• $c_i$ が 'B' のとき、$1\le x_i\le y_i\le 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