Given an array of \(n\) integers, your task is to process \(q\) queries of the following types:

1. update the value at position \(k\) to \(u\)
2. what is the sum of values in range \(\left[a,b\right]\) ?

Input

The first input line has two integers \(n\) and \(q\): the number of values and queries.

The second line has \(n\) integers \(x_1,x_2,\dots ,x_n\): the array values.

Finally, there are \(q\) lines describing the queries. Each line has three integers: either "1 k u" or "2 a b".

Output

Print the result of each query of type 2.

Constraints

\(1 \leq n, q \leq 2 \cdot 10^5\)

\(1 \leq x_i, u \leq 10^9\)

\(1\leq k \leq n\)

\(1 \leq a \leq b \leq n\)

\(1 \leq n, q \leq 1000\) for 50/100.

Example

Input:
8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 3 1
2 1 4

Output:
14
2
11