题目背景

前缀和想必你已经很熟悉了，对于一个长度为$k$的数组$b$，这个数组的前$r$项的和为$S_r=\sum\limits_{i=1}^rb_i$。定义数组$b$的前$r$项“前前缀和”$T_r=\sum\limits_{i=1}^rS_i$。

某天，小魏同学正在做“算法设计与分析”的课后习题，但他遇到了不会的问题，于是走过来向你请教。

题目描述

现给你一个长度为$N$的数组$A$，以及$M$次操作，每次操作格式如下：

1 i x：令$A_i:=x$，其中$:=$表示赋值符号；

2 i：求数组$A$的前缀和数组$^\dagger$的前$i$项的和。

$^\dagger$数组$a$的前缀和数组满足$s_i=\sum\limits_{j=1}^ia_j$

输入格式

本题中每个测试点有多组测试用例。第一行输入一个正整数$T$($1\le T\le 10^4$)，表示测试用例的数量。

每组测试用例的第一行输入两个正整数$N,M$，表示数组$A$的长度和操作数量。

第二行输入$N$个数字，表示数组$A$。

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

保证$\sum N,\sum M\le 2\times 10^5,0\le A_i,x\le10^5$。

输出格式

对于每个操作2，输出一行，表示对应的答案。

样例输入输出

1
5 3
1 2 3 4 5
2 5
1 3 2
2 5

35
32

提示

小魏同学提醒您：

1.使用C++的同学请注意，本题输入数据量较大，请使用scanf输入数据，printf输出数据，或者使用以下三行代码加速cin和cout：

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

若选择后者，请勿混用C和C++的输入输出，否则会导致不可预测的结果。另外，本题请不要使用endl换行。

2.Python可能无法通过本题。