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]$.
Unfortunately, the longer he learns, the fewer he gets.
That means, if he reads books from $l$ to $r$, he will get $a[l] \times L + a[l+1] \times (L-1) + \cdots + a[r-1] \times 2 + a[r]$ ($L$ is the length of [ $l$, $r$ ] that equals to $r - l + 1$).
Now Ryuji has $q$ questions, you should answer him:
$1$. If the question type is $1$, you should answer how much knowledge he will get after he reads books [ $l$, $r$ ].
$2$. If the question type is $2$, Ryuji will change the ith book's knowledge to a new value.
First line contains two integers $n$ and $q$ ($n$, $q \le 100000$).
The next line contains n integers represent $a[i]( a[i] \le 1e9)$ .
Then in next $q$ line each line contains three integers $a$, $b$, $c$, if $a = 1$, it means question type is $1$, and $b$, $c$ represents [ $l$ , $r$ ]. if $a = 2$ , it means question type is $2$ , and $b$, $c$ means Ryuji changes the bth book' knowledge to $c$
For each question, output one line with one integer represent the answer.
5 3 1 2 3 4 5 1 1 3 2 5 0 1 4 5