F2. Dhrumil and Abhishek Game 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Dhrumil and Abhishek are playing a game on an array, Abhishek gives Dhrumil an array $$$a_1, a_2, \dots, a_n$$$ consisting of $$$n$$$ levels.

Abhishek provides Dhrumil with two types of operations:

  • Type 1: Abhishek gives Dhrumil an index and a value, and Dhrumil must update $$$a[\text{index}] = \text{value}$$$.
  • Type 2: Abhishek asks Dhrumil to calculate the weighted sum of points between two indices $$$l$$$ and $$$r$$$: $$$1 * a[l] + 2 * a[l+1] + 3 * a[l+2] + 4 * a[l+3] ....$$$

Your task is to help Dhrumil to accurately find the points, else he will lose the game

Input

The first line of input contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

For each test case:

  • The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$) — the size of the array and the number of queries.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial values of the array.

Then, the next $$$q$$$ lines contain the following types of queries:

  • Type 1: $$$1~\text{index}~\text{value}$$$ — update $$$a[\text{index}] = \text{value}$$$.
  • Type 2: $$$2~l~r$$$ — compute and output the weighted sum $$$S(l, r)$$$.

It is guaranteed that the sum of all $$$n + q$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each query of Type 2, output the weighted sum $$$S(l, r)$$$.

Example
Input
3
5 3
1 2 4 1 5
2 1 5
1 3 10
2 1 5
5 1
1 2 3 4 5
2 1 5
10 8
1 3 2 7 9 6 9 2 6 7
1 1 9
2 1 7
2 1 6
2 3 7
1 6 3
2 3 8
2 4 6
2 1 10
Output
46
64
55
193
130
112
112
34
315