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?
Input data
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).
Output data
For each query print on a separate line the sum of the numbers in the array with indexes from f to t inclusively.
Examples
3 3 1 2 3 ? 1 3 = 3 2 ? 1 3
6 5