Taco Queries

You are given an array of integers and a sequence of queries. There are two types of queries:

1. Query type 1: Given two integers l and r (1-based indices), compute the sum of the subarray from index l to r, inclusive.

2. Query type 2: Given an index i (1-based) and an integer x, update the element at index i to x.

Your task is to process all queries in order. For each query of type 1, output the sum of the specified subarray.

Mathematically, for a query of type 1 with parameters (l) and (r), you are to compute:

[ S = \sum_{i=l}^{r} a_i ]

where (a_i) is the i-th element of the array. Queries of type 2 update the array immediately for any subsequent queries.

inputFormat

The first line contains two space-separated integers (n) and (q), denoting the number of elements in the array and the number of queries, respectively.

The second line contains (n) space-separated integers representing the array elements.

The following (q) lines each contain three space-separated integers. The first integer indicates the query type:

• If the query type is 1, the next two integers are (l) and (r) (with 1-based indexing) for the sum query.
• If the query type is 2, the next two integers are (i) and (x), meaning update the (i)-th element to (x).

outputFormat

For each query of type 1, output the sum of the subarray in a new line. If there are no sum queries, output nothing.## sample

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

6
14