Range Sum Queries

You are given an array of N integers and Q queries. Each query is one of the following two types:

• S L R: Output the sum of the array elements from index L to R (1-indexed).
• U i x: Update the element at index i to the value x.

The task is to process all the queries efficiently. To achieve this, you can use a Binary Indexed Tree (Fenwick Tree). The update and query operations should be performed in \(O(\log N)\) time.

Input Example:

5 3
1 2 3 4 5
S 1 3
U 3 10
S 2 5

Output Example:

6
21

inputFormat

The first line contains two integers N and Q separated by a space, where N is the size of the array and Q is the number of queries.

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

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

• S L R for a sum query, where 1 ≤ L ≤ R ≤ N.
• U i x for an update query, where 1 ≤ i ≤ N and x is the new value.

All input is provided via standard input (stdin).

outputFormat

For each sum query (queries of type S), output the result on a new line. There is no output for update queries. The output should be written to standard output (stdout).

## sample

5 3
1 2 3 4 5
S 1 3
U 3 10
S 2 5

6
21

</p>