# Дерево Фенвика

# Dima and large array

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** (**1** ≤ **i** ≤ **n**, **-1000** ≤ **d** ≤ **1000**), 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

The first line contains two integers **n** and **q** (**1** ≤ **n** ≤ `10`

, ^{6}**1** ≤ **q** ≤ **5** ·`10`

) - the number of elements in array and the total number of operations. In the next line ^{5}**n** numbers are given: `a`

, _{1}`a`

, ..., _{2}`a`

(_{n}**-1000** ≤ `a`

≤ _{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** (**1** ≤ **f**, **t** ≤ **n**).

#### Output

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

3 3 1 2 3 ? 1 3 + 3 -1 ? 1 3

6 5