//poj4047
#include <iostream>
using namespace std;
#define maxn 200100
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
struct Seg {
int l,r,v,c;
int len() {return (r-l+1);}
}a[maxn*3];
void buildtree(int t,int l,int r) {
a[t].l = l;
a[t].r = r;
a[t].v = a[t].c = 0;
if (l==r) return;
int mid=(l+r)>>1;
buildtree(LL(t),l,mid);
buildtree(RR(t),mid+1,r);
}
void up(int t) {
a[t].v = max(a[LL(t)].v,a[RR(t)].v);
}
void down(int t) {
// , lazy ,
if (a[t].l==a[t].r) {
a[t].c = 0;
return;
}
if (a[t].c) {
a[LL(t)].c += a[t].c;
a[RR(t)].c += a[t].c;
a[LL(t)].v += a[t].c; // !! , lazy !
a[RR(t)].v += a[t].c;
a[t].c = 0;
}
}
//
void add(int t,int b,int c,int x) {
if (a[t].l==a[t].r) {
a[t].v += x;
return;
}
if (b==a[t].l && a[t].r==c) {
a[t].c += x;
a[t].v += x;
return;
}
down(t);
int mid=(a[t].l+a[t].r)>>1;
if (c<=mid) add(LL(t),b,c,x);
else if (mid+1<=b) add(RR(t),b,c,x);
else {
add(LL(t),b,mid,x);
add(RR(t),mid+1,c,x);
}
up(t);
}
//
int query(int t,int b,int c) {
down(t);
if (b==a[t].l && a[t].r==c)
return a[t].v;
int mid=(a[t].l+a[t].r)>>1;
if (c<=mid) return query(LL(t),b,c);
else if (mid+1<=b) return query(RR(t),b,c);
else {
return max(query(LL(t),b,mid),query(RR(t),mid+1,c));
}
}
int cas,n,m,k,b,c,r,bb,cc,val[maxn];
int main() {
scanf("%d",&cas);
while (cas--) {
scanf("%d%d%d",&n,&m,&k);
buildtree(1,1,n-k+1);
for (int i=1;i<=n;i++) {
scanf("%d",&val[i]);
b = i-k+1;
if (b<1) b = 1;
c = i;
if (c>n-k+1) c = n-k+1;
add(1,b,c,val[i]);
}
for (int i=1;i<=m;i++) {
scanf("%d%d%d",&r,&b,&c);
if (r==0) {
int tmp = c - val[b];
val[b] = c;
bb = b-k+1;
if (bb<1) bb = 1;
cc = b;
if (cc>n-k+1) cc = n-k+1;
add(1,bb,cc,tmp);
}
else if (r==1) {
int tmp = val[c] - val[b];
val[b] += tmp;
bb = b-k+1;
if (bb<1) bb = 1;
cc = b;
if (cc>n-k+1) cc = n-k+1;
add(1,bb,cc,tmp);
val[c] -= tmp;
bb = c-k+1;
if (bb<1) bb = 1;
cc = c;
if (cc>n-k+1) cc = n-k+1;
add(1,bb,cc,-tmp);
}
else {
printf("%d
",query(1,b,c-k+1));
}
}
}
return 0;
}