The problem you need to solve here is pretty simple. You are give a function f(A, n), where A is an array of integers and n is the number of elements in the array. f(A, n) is defined as follows:

long long f( int A[], int n ) { // n = size of A

long long sum = 0;

for( int i = 0; i < n; i++ )

for( int j = i + 1; j < n; j++ )

sum += A[i] - A[j];

return sum;

}

Given the array A and an integer n, and some queries of the form:

1)      0 x v (0 ≤ x < n, 0 ≤ v ≤ 10⁶), meaning that you have to change the value of A[x] to v.

2)      1, meaning that you have to find f as described above.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing two integers: n and q (1 ≤ n, q ≤ 10⁵). The next line contains n space separated integers between 0 and 10⁶ denoting the array A as described above.

Each of the next q lines contains one query as described above.

Output

For each case, print the case number in a single line first. Then for each query-type "1" print one single line containing the value of f(A, n).

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define mem(x,y) memset(x,y,sizeof(x))

 using namespace std;

 const int INF=0x3f3f3f3f;

 const int MAXN=1e5+;

 typedef long long LL;

 LL a[MAXN],b[MAXN];

 int main(){

     int T,n,q,cnt=;

     scanf("%d",&T);

     while(T--){

         scanf("%d%d",&n,&q);

         LL sum=;

         for(int i=;i<n;i++)scanf("%lld",a+i);

         sum=;

         for(int i=n-;i>=;i--)sum+=a[i],b[i-]=sum;

                 //for(int i=0;i<n;i++)printf("%d ",b[i]);puts("");

         b[n-]=;

         sum=;

         for(int i=;i<n-;i++)sum+=(a[i]*(n-i-)-b[i]);

         mem(b,);

         printf("Case %d:\n",++cnt);

         while(q--){

             int t,x,v;

             scanf("%d",&t);

             if(t){

                 printf("%lld\n",sum);

                 }

             else{

                 scanf("%d%d",&x,&v);

                 sum=sum+(v-a[x])*(n-x-)-x*(v-a[x]);

                 a[x]=v;

             }

         }

     }

     return ;

 }