Dima and array#2941
Mom gave Dima an array of length . This array is not ordinary — it is special. Dima can choose numbers and d~(1 \le i \le n, -1000 \le d \le 1000) and magically assign the value to the element with index .
While Dima is playing with the array, his mom occasionally asks him questions: what is the sum of the array elements with indices from to inclusive? Dima answers these questions effortlessly. Can you?
The first line contains two integers 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 and queries.
The second line contains integers a_1, a_2, \dots, a_n~(-1000 \le a_i \le 1000) — the initial state of the array.
Each of the following lines contains either an operation or a query:
If a line begins with the symbol '', it denotes an assignment operation, followed by the integers and with the constraints specified above.
If a line begins with the symbol '', it denotes a query, followed by the integers and t~(1 \le f, t \le n).
For each query, print the sum of the array elements with indices from to inclusive. Print each answer on a separate line.
مثال 1