Array Queries

You are given an array of N positive integers and Q queries. The queries are of two types:

• Update Query: 1 i x — Update the value at index i to x.
• Range Sum Query: 2 L R — Calculate the sum of the elements from index L to index R (inclusive). Mathematically, you need to compute \[ S = \sum_{k=L}^{R} a[k] \]

Process all queries in order and for each range sum query, output the corresponding sum.

Note: The indices are 1-based. Efficient handling of both types of queries is required. A common approach is to use a Fenwick Tree (also known as a Binary Indexed Tree).

inputFormat

The first line contains two integers N and Q separated by a space.

The second line contains N space-separated integers representing the initial array.

The following Q lines each contain three integers describing a query. For an update query, the format is 1 i x, and for a range sum query, the format is 2 L R.

outputFormat

For each range sum query (i.e. queries beginning with 2), output the computed sum on a new line.

## sample

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

6
21
22

</p>