The first line of input contains two integers $N$, $Q$, where $1 \le N \le 5\, 000\, 000$ is the length of the array and $0 \le Q \le 5\, 000\, 000$ is the number of operations. Then follow $Q$ lines giving the operations. There are two types of operations:
“+ $i$ $\delta $” indicates that $a[i]$ is incremented by $\delta $, where $0 \le i < N$ and $-10^9 \le \delta \le 10^9$ (both are integers)
“? $i$” is a query for the value of $a[0] + a[1] + \ldots + a[i-1]$, where $0 \le i \le N$ (for $i = 0$ this is interpreted as an empty sum)
For each query in the input, output one line giving the answer to that query.
Sample Input 1 | Sample Output 1 |
---|---|
10 4 + 7 23 ? 8 + 3 17 ? 8 |
23 40 |
Sample Input 2 | Sample Output 2 |
---|---|
5 4 + 0 -43 + 4 1 ? 0 ? 5 |
0 -42 |