模板如下：

int lowb(int t){    return t & (-t);}void add(int i,int v){    for( ;i < n;ar[i] += v,i += lowb(i));    return ;}int sum(int i){    int s = 0;    for(;i > 0;s += ar[i],i -= lowb(i));    return s;}

例题：Ryuji doesn't want to study

 

Ryuji is not a good student, and he doesn't want to study. But there are n books he should learn, each book has its knowledge a[i]a[i]a[i].

Unfortunately, the longer he learns, the fewer he gets.

That means, if he reads books from lll to rrr, he will get a[l]×L+a[l+1]×(L−1)+⋯+a[r−1]×2+a[r]a[l] \times L + a[l+1] \times (L-1) + \cdots + a[r-1] \times 2 + a[r]a[l]×L+a[l+1]×(L−1)+⋯+a[r−1]×2+a[r] (LLL is the length of [ lll, rrr ] that equals to r−l+1r - l + 1r−l+1).

Now Ryuji has qqq questions, you should answer him:

111. If the question type is 111, you should answer how much knowledge he will get after he reads books [ lll, rrr ].

222. If the question type is 222, Ryuji will change the ith book's knowledge to a new value.

Input

First line contains two integers nnn and qqq (nnn, q≤100000q \le 100000q≤100000).

The next line contains n integers represent a[i](a[i]≤1e9)a[i]( a[i] \le 1e9)a[i](a[i]≤1e9) .

Then in next qqq line each line contains three integers aaa, bbb, ccc, if a=1a = 1a=1, it means question type is 111, and bbb, ccc represents [ lll , rrr ]. if a=2a = 2a=2 , it means question type is 222 , and bbb, ccc means Ryuji changes the bth book' knowledge to ccc

Output

For each question, output one line with one integer represent the answer.

样例输入

5 31 2 3 4 51 1 32 5 01 4 5

样例输出

108