DEV_CP - Ambitious XOXO

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 ith 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 kth algorithm will be changed to X. It’s not guaranteed that the new value of kth 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*105

1 <= ei, X <= 109

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

Added by:Dr. AddictStein
Date:2021-09-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Dr. AddictStein Research Lab

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.