Preprefix Sum

背景

wyx528：“第一题一定要是水题”

基于这个指导思想，就有了下面这道题……

~~（实在是想不出能有什么题目背景了……）~~

描述

对于一个长度为 $\inline n$ 的序列 $\inline a_1,a_2,\ldots ,a_n$ ，其前缀和（Prefix Sum） $\inline S_i$ 为前 $\inline i$ 个元素的和，即 $\inline \sum_{k=1}^{i}{a_i}$ 。而前缀和的前缀和（Preprefix Sum）就是把前缀和序列 $\inline S_1,S_2,\ldots ,S_n$ 作为原序列，再求一次前缀和。记再次求得的前缀和序列的第 $\inline i$ 位为 $\inline SS_i$ 。

现在给定一个长度为 $\inline n$ 的序列 $\inline a_1,a_2,\ldots ,a_n$ ，有两种操作：

```
Modify i x
```
将 $\inline a_i$ 的值改为 $\inline x$ ；
```
Query i
```
询问 $\inline SS_i$ 的值。

请编写一个程序来实现这两种操作。

输入格式

第一行有两个整数 $\inline n$ 和 $\inline m$ ，分别表示序列长度和操作个数。

接下来的一行有 $\inline n$ 个整数，即给定的序列 $\inline a_1,a_2,\ldots ,a_n$ 。

接下来有 $\inline m$ 行，每行对应一个操作，格式见题目描述。

输出格式

对于每个询问操作，输出一行，表示所询问的 $\inline SS_i$ 的值。

样例输入

5 3
1 2 3 4 5
Query 5
Modify 3 2
Query 5

样例输出

35
32

样例解释

进行了修改操作之后，序列变为 $\inline \{1,2,2,4,5\}$ ，对应的前缀和序列为 $\inline \{1,3,5,9,14\}$ ，故 $\inline SS_5=32$ 。

数据范围与约定

对于所有数据，满足 $\inline 1\leq n,m \leq 100000$ ，且在任意时刻都有 $\inline 0\leq a_i\leq 100000$ 。

提交代码