背景

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,有两种操作:

  1. Modify i x

    \inline a_i的值改为\inline x

  2. 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