//segment tree(RMQ)
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ll int
const int maxn=100000;
int t[4*maxn],tt[4*maxn];
int lazyx[4*maxn],lazyy[4*maxn]; //for lazy propagation(range update)
void pushx(int v)
{
lazyx[2*v+1]+=lazyx[v];
lazyx[2*v+2]+=lazyx[v];
t[2*v+1]+=lazyx[v];
t[2*v+2]+=lazyx[v];
lazyx[v]=0;
}
void pushy(int v)
{
lazyy[2*v+1]+=lazyy[v];
lazyy[2*v+2]+=lazyy[v];
tt[2*v+1]+=lazyy[v];
tt[2*v+2]+=lazyy[v];
lazyy[v]=0;
}
int constructx(int* arr, int st, int end, int si)
{
if(st==end)
{
t[si] = arr[st];
return t[si];
}
int mid = (st + end)/2;
constructx(arr,st, mid, 2*si + 1);
constructx(arr,mid+1, end, 2*si + 2);
t[si] = min(t[2*si+1],t[2*si+2]);
return t[si];
}
int queryx(int qs, int qe, int l, int r, int si)
{
if(qs<=l && qe>=r)
return t[si];
if(qs>r || qe<l)
return INT_MAX; //change acc. to question
else
{
pushx(si);
int mid = (l + r)/2;
int sum = min(queryx(qs, qe, l, mid, 2*si + 1), queryx(qs, qe, mid+1, r, 2*si + 2));
return sum;
}
}
void updatex( int x, int l, int r,int tl, int tr, int si)
{
if(l>r)
return;
if(l==tl && r==tr)
{
t[si] += x;
lazyx[si] += x;
}
else
{
pushx(si);
int mid = (l + r)/2;
updatex(x, tl, min(mid,tr),l, mid , 2*si + 1);
updatex(x, max(mid+1,tl),tr, mid+1, r, 2*si + 2);
t[si] = min(t[2*si+1] , t[2*si+2]);
}
}
int constructy(int* arr, int st, int end, int si)
{
if(st==end)
{
tt[si] = arr[st];
return tt[si];
}
int mid = (st + end)/2;
constructy(arr,st, mid, 2*si + 1);
constructy(arr,mid+1, end, 2*si + 2);
tt[si] = min(tt[2*si+1],tt[2*si+2]);
return tt[si];
}
int queryy(int qs, int qe, int l, int r, int si)
{
if(qs<=l && qe>=r)
return tt[si];
if(qs>r || qe<l)
return INT_MAX; //change acc. to question
pushy(si);
int mid = (l + r)/2;
int sum = min(queryy(qs, qe, l, mid, 2*si + 1), queryy(qs, qe, mid+1, r, 2*si + 2));
return sum;
}
void updatey( int x, int l, int r,int tl, int tr, int si)
{
if(l>r)
return;
if(l==tl && r==tr)
{
tt[si] += x;
lazyy[si] += x;
}
else
{
pushy(si);
int mid = (l + r)/2;
updatey(x, tl, min(mid,tr),l, mid , 2*si + 1);
updatey(x, max(mid+1,tl),tr, mid+1, r, 2*si + 2);
tt[si] = min(tt[2*si+1] , tt[2*si+2]);
}
}
void solve()
{ int n,q;
cin>>n>>q;
int* arr = new int[n];
int sum=0;
for(int i=0; i<n; i++)
{
cin>>arr[i];
sum+=arr[i];
}
int prefix[n],sufix[n];
prefix[0]=arr[0];
sufix[n-1]=arr[n-1];
for (int i = 1; i < n; ++i)
{
prefix[i]=prefix[i-1]+arr[i];
sufix[n-i-1]=sufix[n-i]+arr[n-i-1];
}
for(int i=0; i<4*maxn; i++)
{ t[i] = 0;
lazyx[i]=0;
tt[i] = 0;
lazyy[i] = 0;
}
constructx(prefix, 0, n-1, 0);
constructy(sufix, 0, n-1, 0);
while(q--)
{
char ch;
cin>>ch;
if(ch=='Q')
{
int qs,qe;
cin>>qs>>qe;
qs--;
qe--;
int s1=0,s2=0;
if(qs!=0)
s1= queryx(0, qs-1, 0, n-1, 0);
if(qe!=n-1)
s2= queryy(qe+1,n-1, 0, n-1, 0);
//cout<<sum<<" "<<s1<<" "<<s2<<endl;
if(s1>0)
s1=0;
if(s2>0)
s2=0;
cout<<sum-s1-s2<<endl;
}
else
{
int add,index;
cin>>index;
cin>>add;
index--;
int temp=add;
sum=sum-arr[index]+add;
add=add-arr[index];
arr[index]=temp;
updatex(add,index,n-1, 0, n-1, 0);
updatey(add,0,index,0,n-1,0);
}
}
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int t;
cin>>t;
while(t--)
solve();
}