Extra
Time
前缀前缀和 Time:1s Memory:50M AC:0% Submit:3

题目描述

对于一个长度为n的序列a_1,a_2,\cdots,a_n,其前缀和S_i为前i个元素的和,即\sum_{k=1}^{i}{a_i}。而前缀和的前缀和就是把前缀和序列S_1,S_2,\cdots,S_n作为原序列,再求一次前缀和。记再次求得的前缀和序列的第i位为SS_i
现在给定一个长度为i的序列a_1,a_2,\cdots,a_n ,有两种操作:
1.Modify i xa_i的值改为x

2.Query i询问SS_i的值。
请编写一个程序来实现这两种操作。

输入格式

第一行有两个整数nmm表示操作个数。 接下来的一行有n个整数,即给定的序列a_1,a_2,\cdots,a_n
接下来有m行,每行对应一个操作,格式见题目描述。

输出格式

对于每个询问操作,输出一行,表示所询问的SS_i的值。

样例输入

5 3

1 2 3 4 5

Query 5

Modify 3 2

Query 5

样例输出

35

32

数据范围

对于 30%的数据,n,m<=200

对于 60%的数据,n,m<=5000

对于 100%的数据,n,m<=100000