#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 100005;
namespace SegmentTree{
#define Left (node*2)
#define Right (node*2+1)
#define mid ((lo+hi)/2)
ll lazy[maxn*5];
ll minTree[maxn*5];
ll maxTree[maxn*5];
void build(int node, int lo, int hi){
minTree[node] = maxTree[node] = lazy[node] = 0;
if(lo == hi) return;
build(Left, lo, mid);
build(Right, mid+1, hi);
}
void lazyPropagation(int node, int lo, int hi){
minTree[node] += lazy[node]; maxTree[node] += lazy[node];
if(lo != hi) {lazy[Left] += lazy[node]; lazy[Right] += lazy[node];}
lazy[node] = 0;
}
void updateRange(int node, int lo, int hi, int i, int j, ll val){
lazyPropagation(node,lo,hi);
if(lo>hi || lo>j || hi<i) return;
if(lo>=i && hi<=j) {lazy[node] += val; lazyPropagation(node,lo,hi); return;}
updateRange(Left,lo,mid,i,j,val);
updateRange(Right,mid+1,hi,i,j,val);
minTree[node] = min(minTree[Left], minTree[Right]);
maxTree[node] = max(maxTree[Left], maxTree[Right]);
}
ll queryMax(int node, int lo, int hi, int i, int j){
if(lo>hi || lo>j || hi<i) return LLONG_MIN;
lazyPropagation(node,lo,hi);
if(lo>=i && hi<=j) return maxTree[node];
ll p1 = queryMax(Left, lo, mid,i,j);
ll p2 = queryMax(Right,mid+1,hi,i,j);
return max(p1, p2);
}
ll queryMin(int node, int lo, int hi, int i, int j){
if(lo>hi || lo>j || hi<i) return 0;
lazyPropagation(node,lo,hi);
if(lo>=i && hi<=j) return minTree[node];
ll p1 = queryMin(Left, lo, mid,i,j);
ll p2 = queryMin(Right,mid+1,hi,i,j);
return min(p1, p2);
}
}
using namespace SegmentTree;
ll a[maxn];
int main(){
int t;
scanf("%d", &t);
for(int cs=1; cs<=t; cs++){
int n, q;
scanf("%d %d", &n, &q);
build(1, 1, n);
for(int i=1; i<=n; i++){
scanf("%lld", &a[i]);
updateRange(1, 1, n, i, n, a[i]);
}
for(int i=1; i<=q; i++){
char cmd;
scanf(" %c", &cmd);
if(cmd == 'U'){
int x; ll y;
scanf("%d %lld",&x, &y);
updateRange(1, 1, n, x, n, y - a[x]);
a[x] = y;
}
else{
int l, r;
scanf("%d %d",&l, &r);
ll ret = queryMax(1, 1, n, r, n);
ret -= queryMin(1, 1, n, 1, l-1);
printf("%lld\n", ret);
}
}
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nIGludApjb25zdCBpbnQgbWF4biA9IDEwMDAwNTsKIApuYW1lc3BhY2UgU2VnbWVudFRyZWV7CiAgICAjZGVmaW5lIExlZnQgKG5vZGUqMikKICAgICNkZWZpbmUgUmlnaHQgKG5vZGUqMisxKQogICAgI2RlZmluZSBtaWQgKChsbytoaSkvMikKIAogICAgbGwgbGF6eVttYXhuKjVdOwogICAgbGwgbWluVHJlZVttYXhuKjVdOwogICAgbGwgbWF4VHJlZVttYXhuKjVdOwogCiAgICB2b2lkIGJ1aWxkKGludCBub2RlLCBpbnQgbG8sIGludCBoaSl7CiAgICAgICAgbWluVHJlZVtub2RlXSA9IG1heFRyZWVbbm9kZV0gPSBsYXp5W25vZGVdID0gMDsKICAgICAgICBpZihsbyA9PSBoaSkgcmV0dXJuOwogICAgICAgIGJ1aWxkKExlZnQsIGxvLCBtaWQpOwogICAgICAgIGJ1aWxkKFJpZ2h0LCBtaWQrMSwgaGkpOwogICAgfQogCiAgICB2b2lkIGxhenlQcm9wYWdhdGlvbihpbnQgbm9kZSwgaW50IGxvLCBpbnQgaGkpewogICAgICAgIG1pblRyZWVbbm9kZV0gKz0gbGF6eVtub2RlXTsgbWF4VHJlZVtub2RlXSArPSBsYXp5W25vZGVdOwogICAgICAgIGlmKGxvICE9IGhpKSB7bGF6eVtMZWZ0XSArPSBsYXp5W25vZGVdOyBsYXp5W1JpZ2h0XSArPSBsYXp5W25vZGVdO30KICAgICAgICBsYXp5W25vZGVdID0gMDsKICAgIH0KIAogICAgdm9pZCB1cGRhdGVSYW5nZShpbnQgbm9kZSwgaW50IGxvLCBpbnQgaGksIGludCBpLCBpbnQgaiwgbGwgdmFsKXsKICAgICAgICBsYXp5UHJvcGFnYXRpb24obm9kZSxsbyxoaSk7CiAgICAgICAgaWYobG8+aGkgfHwgbG8+aiB8fCBoaTxpKSByZXR1cm47CiAgICAgICAgaWYobG8+PWkgJiYgaGk8PWopIHtsYXp5W25vZGVdICs9IHZhbDsgbGF6eVByb3BhZ2F0aW9uKG5vZGUsbG8saGkpOyByZXR1cm47fQogICAgICAgIHVwZGF0ZVJhbmdlKExlZnQsbG8sbWlkLGksaix2YWwpOwogICAgICAgIHVwZGF0ZVJhbmdlKFJpZ2h0LG1pZCsxLGhpLGksaix2YWwpOwogICAgICAgIG1pblRyZWVbbm9kZV0gPSBtaW4obWluVHJlZVtMZWZ0XSwgbWluVHJlZVtSaWdodF0pOwogICAgICAgIG1heFRyZWVbbm9kZV0gPSBtYXgobWF4VHJlZVtMZWZ0XSwgbWF4VHJlZVtSaWdodF0pOwogICAgfQogCiAgICBsbCBxdWVyeU1heChpbnQgbm9kZSwgaW50IGxvLCBpbnQgaGksIGludCBpLCBpbnQgail7CiAgICAgICAgaWYobG8+aGkgfHwgbG8+aiB8fCBoaTxpKSByZXR1cm4gTExPTkdfTUlOOwogICAgICAgIGxhenlQcm9wYWdhdGlvbihub2RlLGxvLGhpKTsKICAgICAgICBpZihsbz49aSAmJiBoaTw9aikgcmV0dXJuIG1heFRyZWVbbm9kZV07CiAgICAgICAgbGwgcDEgPSBxdWVyeU1heChMZWZ0LCBsbywgbWlkLGksaik7CiAgICAgICAgbGwgcDIgPSBxdWVyeU1heChSaWdodCxtaWQrMSxoaSxpLGopOwogICAgICAgIHJldHVybiBtYXgocDEsIHAyKTsKICAgIH0KIAogICAgbGwgcXVlcnlNaW4oaW50IG5vZGUsIGludCBsbywgaW50IGhpLCBpbnQgaSwgaW50IGopewogICAgICAgIGlmKGxvPmhpIHx8IGxvPmogfHwgaGk8aSkgcmV0dXJuIDA7CiAgICAgICAgbGF6eVByb3BhZ2F0aW9uKG5vZGUsbG8saGkpOwogICAgICAgIGlmKGxvPj1pICYmIGhpPD1qKSByZXR1cm4gbWluVHJlZVtub2RlXTsKICAgICAgICBsbCBwMSA9IHF1ZXJ5TWluKExlZnQsIGxvLCBtaWQsaSxqKTsKICAgICAgICBsbCBwMiA9IHF1ZXJ5TWluKFJpZ2h0LG1pZCsxLGhpLGksaik7CiAgICAgICAgcmV0dXJuIG1pbihwMSwgcDIpOwogICAgfQp9CnVzaW5nIG5hbWVzcGFjZSBTZWdtZW50VHJlZTsKIApsbCBhW21heG5dOwppbnQgbWFpbigpewogICAgaW50IHQ7CiAgICBzY2FuZigiJWQiLCAmdCk7CiAKICAgIGZvcihpbnQgY3M9MTsgY3M8PXQ7IGNzKyspewogICAgICAgIGludCBuLCBxOwogICAgICAgIHNjYW5mKCIlZCAlZCIsICZuLCAmcSk7CiAgICAgICAgCiAgICAgICAgYnVpbGQoMSwgMSwgbik7CiAgICAgICAgZm9yKGludCBpPTE7IGk8PW47IGkrKyl7CiAgICAgICAgICAgIHNjYW5mKCIlbGxkIiwgJmFbaV0pOwogICAgICAgICAgICB1cGRhdGVSYW5nZSgxLCAxLCBuLCBpLCBuLCBhW2ldKTsKICAgICAgICB9CiAKICAgICAgICBmb3IoaW50IGk9MTsgaTw9cTsgaSsrKXsKICAgICAgICAgICAgY2hhciBjbWQ7CiAgICAgICAgICAgIHNjYW5mKCIgJWMiLCAmY21kKTsKIAogICAgICAgICAgICBpZihjbWQgPT0gJ1UnKXsKICAgICAgICAgICAgICAgIGludCB4OyBsbCB5OwogICAgICAgICAgICAgICAgc2NhbmYoIiVkICVsbGQiLCZ4LCAmeSk7CiAgICAgICAgICAgICAgICB1cGRhdGVSYW5nZSgxLCAxLCBuLCB4LCBuLCB5IC0gYVt4XSk7CiAgICAgICAgICAgICAgICBhW3hdID0geTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgaW50IGwsIHI7CiAgICAgICAgICAgICAgICBzY2FuZigiJWQgJWQiLCZsLCAmcik7CiAgICAgICAgICAgICAgICBsbCByZXQgPSBxdWVyeU1heCgxLCAxLCBuLCByLCBuKTsKICAgICAgICAgICAgICAgIHJldCAtPSBxdWVyeU1pbigxLCAxLCBuLCAxLCBsLTEpOwogICAgICAgICAgICAgICAgcHJpbnRmKCIlbGxkXG4iLCByZXQpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9