Cho dãy ~a~ gồm ~n~ phần tử nguyên dương ~a[1],a[2],...a[n]~. Cho ~q~ thao tác thực hiện lần lượt, thao tác thứ ~i~ sẽ có một trong hai loại truy vấn như sau:

• ~1~ ~i~ ~v~ - gán ~a[i]=v~.
• ~2~ ~l~ ~r~ - in ra tổng các phần tử từ chỉ số ~l~ đến ~r~ tức là ~a[l]+a[l+1]+...+a[r-1]+a[r]~.

Yêu cầu: Thực hiện tất cả lần lượt ~q~ truy vấn và chỉ in ra kết quả của thao tác thứ ~2~.

Input

• Dòng thứ nhất gồm hai số nguyên dương ~n,q~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a[1],a[2],...,a[n]~ ~(1 \leq a[i] \leq 10^9)~.
• ~q~ dòng tiếp theo. Mỗi dòng gồm 3 số : ~1~ ~i~ ~v~ ~(1 \leq i,v \leq n)~ hoặc ~2~ ~l~ ~r~ ~(1 \leq l \leq r \leq n)~.

Output

• In ra kết quả của các truy vấn loại ~2~.

Scoring

• Subtask ~1~ ~(40\%)~: ~n,q \leq 10^3~.
• Subtask ~2~ ~(60\%)~: ~n,q \leq 10^5~.

Example input 1

6 6
5 3 7 9 6 2
2 1 6
1 3 10
2 2 4
1 6 8
2 4 6
2 1 3

Example output 1

32
22
23
18