Dima and large array

Mother gave Dima a special array of length $n$ as a present. Dima can choose any index $i(1\le i\le n)$ and add a value $d(1\le i\le n,-1000\le d\le 1000)$ to the element at that index. Dima enjoys playing with his array, and from time to time, his mother asks him questions about it. Specifically, she asks for the sum of the numbers in the array within a given range of indices from $f$ to $t$ (inclusive). However, since she is very busy, she can ask no more than $1000$ questions. Dima handles this task easily, but can you?

Input

The first line contains two integers $n$ and $q(1\le n\le 10^6,1\le q\le 5\cdot 10^5)$ — the number of elements in 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)$ — the initial state of the array. The following $q$ lines contain the operations and queries. The first character in the line can be either '$+$' or '$?$'. If a line starts with '$+$', it is an assignment operation, followed by the values $i$ and $d$. If a line starts with '$?$', it is a query, followed by the values $f$ and $t(1\le f,t\le n)$.

Output

For each query, print the sum of the numbers in the array within the specified range of indices from $f$ to $t$ (inclusive) on a separate line.

Examples