eolymp
bolt
Try our new interface for solving problems
Problems

Dima and large array

Dima and large array

Time limit 7 seconds
Memory limit 256 MiB

Mother gave Dima as a present an array of length n. The array is not simple, but special. Dima can choose two numbers i and d (1in, -1000d1000), and from the element with index i magically add d. Dima plays with his array, and mother gives his questions time from time - what is the sum of all the numbers in array with indexes from f to t inclusive? However, the mother is very busy and can not ask questions as often as usual - all she asked no more than 1000 questions. Dima easily managed this problem, but what about you?

Input data

The first line contains two integers n and q (1n10^6, 1q5 ·10^5) - the number of elements in array and the total number of operations. In the next line n numbers are given: a[1], a[2], ..., a[n] (-1000a[i]1000) - the initial state of array. The next q lines contain the operations and queries. The first character in the line can be either + or ?. If the line starts with +, this is an assignment operation. Next values are i and d, their restrictions are given earlier. If the line starts with ?, this is a query. Then go numbers f and t (1f, tn).

Output data

For each query print on a separate line the sum of the numbers in array with indexes from f to t inclusive.

Examples

Input example #1
3 3
1 2 3
? 1 3
+ 3 -1
? 1 3
Output example #1
6
5
Author Egor Kulikov
Source Winter School Kharkov 2012