Range Sum Queries and Point Updates

You are given an array of (N) integers and then a sequence of (Q) queries. There are two types of queries:

1. Query of the form (1\ L\ R): Compute and output the sum of the array elements from index (L) to (R) (1-indexed).
2. Query of the form (2\ L\ V): Update the element at index (L) (1-indexed) to the value (V).

Use an efficient data structure such as a segment tree to perform both operations in (O(\log N)) time per query.

For example, given an array [1, 2, 3, 4, 5] and the queries:

1 1 3 2 2 10 1 1 3 1 2 5

The results for the sum queries are: 6, 14, 22.

Note: Indexing is 1-based.

inputFormat

The input is given in the following format from standard input (stdin):

The first line contains two integers (N) and (Q), separated by space. The second line contains (N) space-separated integers representing the array. Each of the next (Q) lines contains a query. A query is either of the form:

• For sum query: 1 L R
• For update query: 2 L V

It is guaranteed that the queries are valid and follow the above format.

outputFormat

For each sum query (type 1), output the result on a separate line to standard output (stdout).## sample

5 4
1 2 3 4 5
1 1 3
2 2 10
1 1 3
1 2 5

6
14
22