对于一个数组 AAA，其前缀和每一个元素的前缀和（Prefix Sum）定义为：Si=∑k=1iAiS_i=\sum_{k=1}^{i}A_iSi=∑k=1iAi。
可以发现，对于一个新数组，依次加入每个位置的前缀和 SiS_iSi，也可以构成一个与 AAA 大小相等的数组 SSS。
前前缀和(Pre-prefix Sum) 则把 SSS 数组作为原数组再进行前缀和操作，记再次求得前缀和第 iii 个是 SSiSS_iSSi。
给定一个长度为 nnn 的数组 AAA，有如下两种操作：
1 i x
2 i
第一行给出两个整数 n,mn,mn,m。分别表示序列长度和操作个数；
接下来一行 nnn 个数，即给定的数组 A1,A2,...,AnA_1,A_2,...,A_nA1,A2,...,An；
接下来 mmm 行，每行对应一个操作，格式见题目描述。
对于每个询问操作，输出一行，表示所询问的 SSiSS_iSSi 的值。
5 3 1 2 3 4 5 2 5 1 3 2 2 5
35 32
1≤n,m≤1051\le n,m \le 10^51≤n,m≤105
在任意时刻 0≤Ai≤1050\le A_i\le 10^50≤Ai≤105