Range Sum Queries with Updates

You are given an array of n integers. You need to process q queries. There are two types of queries:

• 1 x y: Update the element at 1-indexed position x to y.
• 2 l r: Compute the sum from index l to r (both inclusive). Note that the sum is defined as \(\sum_{i=l}^{r} a_i\).

You must implement these operations efficiently. For example, a segment tree data structure can be used to support both update and range sum queries in \(O(\log n)\) time.

The input is given via standard input, and the output should be printed to standard output. Each output should be printed on a new line.

inputFormat

The first line contains two integers n and q the number of elements and the number of queries respectively. The second line contains n space-separated integers representing the array.

Each of the following q lines contains a query in one of the following formats:

• 1 x y — update the element at position x to y.
• 2 l r — output the sum of elements from position l to r.

outputFormat

For each query of the second type, print the resulting sum on a new line.

## sample

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

6
22
33

</p>