Life is a growth.
If we stop growing,
Technically and spiritually,
We are as good as DEAD
- Morihei Ueshiba

Our hero XOXO_Bunnyface is a programmer. He loves to append his name just after the precious word, “Competitive”. He is not much intelligent, nor much logical. But he loves to learn new algorithms and he loves to practice.

The world he is currently living has N algorithms. You will be given an array of efficiency of size N, where if the i^th element is x, that means the initial efficiency of XOXO on that algorithm is x.

XOXO will do M tasks in this month in order. The tasks will be of two types.

1 K X

That means, the efficiency of XOXO on the k^th algorithm will be changed to X. It’s not guaranteed that the new value of k^th index will be greater than the initial value. The efficiency might also decrease. XOXO is a human being after all.

2 A B

There will be a contest arranged on which the efficiency of XOXO will be tested on the algorithms in the range between A and Binclusive. In that case, you have to tell the performance of XOXO on that contest which will be the sum of efficiencies inside that range.

Input

The first input line has two integers N and M: the number of values and tasks. The second line has N integers e1, e2 ... eN: the values of the array of efficiency. Finally, there are M lines describing the tasks list. Each line has three integers: either "1 K X" or "2 A B"

Output

Print the result of each query of type 2.

Constraints

1 <= N, M <= 2*10⁵

1 <= e_i, X <= 10⁹

1 <= k <= N

1 <= A, B <= N

Samples

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

Output:
15
8
10
8