#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Point Add Range Sum - Classic Problems | Repovive

CLS53. Point Add Range Sum

2s256 MB

Given an array, process point-add updates and range-sum queries.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$-10^9 \le a_i, x \le 10^9$
$1 \le l \le r \le n$

Input

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ op_1 \\ op_2 \\ \vdots \\ op_q \end{array}

op_j \in \left\{ \begin{array}{lll} 1 & i & x \\ 2 & l & r \end{array} \right.

Output

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_k \end{array}

k = \#\{\text{type } 2 \text{ queries}\}

Samples

Input

Explanation

The three printed sums are 6, then 16 after adding to position 2, then 4 after subtracting from position 5.

Output

6
16
4

Input

Explanation

The only position starts at 0, then becomes 3, so the printed values are 0 and 3.

Output

0
3

Input

Explanation

The first query totals 3; after adding 10 to position 3, the whole array totals 12.

Output

3
12

$1 \le n, q \le 2 \cdot 10^5$
$-10^9 \le a_i, x \le 10^9$
$1 \le l \le r \le n$

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ op_1 \\ op_2 \\ \vdots \\ op_q \end{array}

op_j \in \left\{ \begin{array}{lll} 1 & i & x \\ 2 & l & r \end{array} \right.

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_k \end{array}

k = \#\{\text{type } 2 \text{ queries}\}