Update Subarray Sums

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

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

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.