Problems

# Dima and array

# Dima and array

Mother presented Dima an array of length $n$. This array is not simple, but special. Dima can choose two numbers $i$ and $d\:(1 \le i \le n, -1000 \le d \le 1000)$, and the element at index $i$ magically becomes equal to $d$. Dima plays with his array, and from time to time Mom asks him questions --- what is the sum of all numbers in the array with indices from $f$ to $t$ inclusive? Dima easily handled these questions. Can you?
\InputFile
The first line contains two integers $n$ and $q\:(1 \le n \le 5 \cdot 10^5, 1 \le q \le 10^5)$ --- the number of elements in the array and the total number of operations. The next line contains $n$ integers: $a_1, a_2, ..., a_n\: (-1000 \le a_i \le 1000)$ representing the initial state of the array. The following $q$ lines contain operations and queries. The first character of each line can be either $=$ or $?$. If the line starts with $=$, it is an assignment operation. Next values are $i$ and $d$, their restrictions are given earlier. If the line starts with $?$, it is a query, followed by $f$ and $t\:(1 \le f, t \le n)$.
\OutputFile
For each query print on a separate line the sum of the numbers in the array with indexes from $f$ to $t$ inclusively.

Input example #1

3 3 1 2 3 ? 1 3 = 3 2 ? 1 3

Output example #1

6 5