Problem Statement

You are given an array ~a~ of ~n~ integers. You are also given ~q~ queries of the following forms:

• Type 1: ~1~ ~i~ ~v~ - update the values of ~a_i~ to become ~v~
• Type 2: ~2~ ~l~ ~r~ - determine the sum of the range ~l~ to ~r~, i.e. ~a_l + a_{l+1} + ... + a_r~

Input Statement

Your first line will contain two space-separated integers ~n~ and ~q~. Your next line will contain ~n~ space-separated integers representing ~a~. Your next ~q~ lines will contain two space-separated integers each representing the queries described.

Output Statement

For each type 2 query you should output a new line containing the sum of the range described.

Constraints

• ~1 \leq n, q \leq 10^4~
• ~1 \leq l \leq r \leq n~ queries are ~1~-indexed
• ~-10^9 \leq a_i \leq 10^9~ (including after updates)

Sample Cases

Input 1

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

Output 1

40
40
-4

Explanation 1

After updating ~a_5~ to become -10, the array is 1 2 3 4 -10 6 7 8 9 10 The sum from 1 to 10 is 40. Nothing happens when updating ~a_1~ to 1. The sum from 1 to 10 is still 40. The sum from 5 to 6 is -10 + 6 = -4.