#include<bits/stdc++.h>
using namespace std;
long long num,c;
struct seg2{
	vector<long long> a,v;
	void build(int rt,int l,int r){
		if(l==r){
			v[rt]=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(rt<<1,l,mid);
		build(rt<<1|1,mid+1,r);
		v[rt]=max(v[rt<<1],v[rt<<1|1]);
	}
	void update(int rt,int l,int r,int ll,long long xx){
		if(l==r){
			v[rt]=xx;
			return;
		}
		int mid=(l+r)>>1;
		if(xx<=mid)update(rt<<1,l,mid,ll,xx);
		else update(rt<<1|1,mid+1,r,ll,xx);
		v[rt]=max(v[rt<<1],v[rt<<1|1]);
		return;
	}
	void change(int x,long long y){
		if(a[x]==y)return;
		a[x]=y;
		update(1,1,num,x,y);
		return;
	}
	long long query(int rt,int l,int r,int ll,int rr){
		if(l>rr||r<ll)return 0;
		if(l>=ll&&r<=rr)return v[rt];
		int mid=(l+r)>>1;
		return max(query(rt<<1,l,mid,ll,rr),query(rt<<1|1,mid+1,r,ll,rr));
	}
}tr2,tr3;
struct seg1{
	vector<long long> a,b,f,g,lazyf,lazyg,fl;
	struct node{
		long long fmx,gmx,ans;
		node operator +(const node bb)const{
			node rtn;
			rtn.fmx=max(fmx,bb.fmx);
			rtn.gmx=max(gmx,bb.gmx);
			rtn.ans=max(ans,bb.ans);
			rtn.ans=max(rtn.ans,fmx+bb.gmx);
			return rtn;
		}
	};
	vector<node> v;
	void pushdown(int rt){
		if(lazyf[rt]){
			lazyf[rt<<1]+=lazyf[rt];
			lazyf[rt<<1|1]+=lazyf[rt];
			v[rt<<1].fmx+=lazyf[rt];
			v[rt<<1|1].fmx+=lazyf[rt];
			if(!fl[rt<<1])v[rt<<1].ans+=lazyf[rt];
			if(!fl[rt<<1|1])v[rt<<1|1].ans+=lazyf[rt];
			lazyf[rt]=0;
		}
		if(lazyg[rt]){
			lazyg[rt<<1]+=lazyg[rt];
			lazyg[rt<<1|1]+=lazyg[rt];
			v[rt<<1].gmx+=lazyg[rt];
			v[rt<<1|1].gmx+=lazyg[rt];
			if(!fl[rt<<1])v[rt<<1].ans+=lazyg[rt];
			if(!fl[rt<<1|1])v[rt<<1|1].ans+=lazyg[rt];
			lazyg[rt]=0;
		}
	}
	void build(int rt,int l,int r){
		if(l==r){
			v[rt].fmx=f[l];
			v[rt].gmx=g[l];
			v[rt].ans=0;
			fl[rt]=1;
			return;
		}
		int mid=(l+r)>>1;
		build(rt<<1,l,mid);
		build(rt<<1|1,mid+1,r);
		v[rt]=v[rt<<1]+v[rt<<1|1];
		return; 
	} 
	node query1(int rt,int l,int r,int ll){
		if(l==r)return v[rt];
		int mid=(l+r)>>1;
		node tmp=v[rt<<1];
		tmp.ans=tmp.gmx=0;
		pushdown(rt);
		node tttmp=query1(rt<<1,l,mid,ll);
		tttmp=tttmp+v[rt<<1|1];
//		cout<<tttmp.ans<<endl;
		tttmp=tmp+query1(rt<<1|1,mid+1,r,ll);
//		cout<<tttmp.ans<<endl;
//		cout<<v[rt].ans<<endl;
		if(ll<=mid)return query1(rt<<1,l,mid,ll)+v[rt<<1|1];
		else return tmp+query1(rt<<1|1,mid+1,r,ll);
	}
	node query2(int rt,int l,int r,int ll){
		if(l==r)return v[rt];
		int mid=(l+r)>>1;
		node tmp=v[rt<<1|1];
		tmp.ans=tmp.fmx=0;
		pushdown(rt);
		if(ll<=mid)return query2(rt<<1,l,mid,ll)+tmp;
		else return v[rt<<1]+query2(rt<<1|1,mid+1,r,ll);
	}
	node query3(int rt,int l,int r,int ll){
		if(l>ll){
			node tmp=v[rt];
			tmp.fmx=tmp.ans=0;
			return tmp;
		}
		if(r<=ll){
			node tmp=v[rt];
			tmp.gmx=tmp.ans=0;
			return tmp;
		}
		int mid=(l+r)>>1;
		pushdown(rt);
		return query3(rt<<1,l,mid,ll)+query3(rt<<1|1,mid+1,r,ll);
	}
	node query4(int rt,int l,int r,int ll,int rr){
		if(l>=ll&&r<=rr)return v[rt];
		if(l>rr){
			node tmp;
			tmp.gmx=tmp.fmx=tmp.ans=0;
			return tmp;
		}
		if(r<ll){
			node tmp=v[rt];
			tmp.gmx=tmp.ans=0;
			return tmp;
		}
		int mid=(l+r)>>1;
		pushdown(rt);
		return query4(rt<<1,l,mid,ll,rr)+query4(rt<<1|1,mid+1,r,ll,rr);
	}
	long long Query1(int x){
		node rtn=query1(1,1,c,x);
		long long tmp=max(rtn.ans,rtn.fmx);
		return max(tmp,rtn.gmx);
	}
	long long Query2(int x){
		node rtn=query2(1,1,c,x);
		long long tmp=max(rtn.ans,rtn.fmx);
		return max(tmp,rtn.gmx);
	}
	long long Query3(int l,int r){
		node rtn=query3(1,1,c,r);
		long long tmp=max(0ll,rtn.fmx)+max(0ll,rtn.gmx);
		rtn=query4(1,1,c,l,r);
		tmp=max(tmp,rtn.gmx);
		tmp=max(tmp,rtn.fmx);
		tmp=max(tmp,rtn.ans);
		return tmp;
	}
	void update1(int rt,int l,int r,int ll,int rr,long long xx){
		if(l>rr||r<ll)return;
		if(l>=ll&&r<=rr){
			lazyg[rt]+=xx;
			v[rt].gmx+=xx;
			if(l!=r)v[rt].ans+=xx;
			return;
		}
		int mid=(l+r)>>1;
		pushdown(rt);
		update1(rt<<1,l,mid,ll,rr,xx);
		update1(rt<<1|1,mid+1,r,ll,rr,xx);
		v[rt]=v[rt<<1]+v[rt<<1|1];
	}
	void update2(int rt,int l,int r,int ll,int rr,long long xx){
		if(l>rr||r<ll)return;
		if(l>=ll&&r<=rr){
			lazyf[rt]+=xx;
			v[rt].fmx+=xx;
			if(l!=r)v[rt].ans+=xx;
			return;
		}
		int mid=(l+r)>>1;
		pushdown(rt);
		update2(rt<<1,l,mid,ll,rr,xx);
		update2(rt<<1|1,mid+1,r,ll,rr,xx);
		v[rt]=v[rt<<1]+v[rt<<1|1];
	}
	void bbuild(){
		for(int i=1;i<=c;i++)f[i]=f[i-1]+b[i];
		for(int i=c;i;i--)g[i]=g[i+1]+a[i];
		build(1,1,c);
		return;
	}
	void change1(int x,long long y){
		if(a[x]==y)return;
		update1(1,1,c,1,x,y-a[x]);
		a[x]=y;
	}
	void change2(int x,long long y){
		if(b[x]==y)return;
		update2(1,1,c,x,c,y-b[x]);
		b[x]=y;
	}
}tr1;
struct seg0{
	struct node{
		long long ls,rs,ss,mx;
		node operator +(const node bb){
			node rtn;
			rtn.ls=max(ls,ss+bb.ls);
			rtn.rs=max(ss+bb.rs,rs);
			rtn.ss=ss+bb.ss;
			rtn.mx=max(mx,bb.mx);
			rtn.mx=max(rtn.mx,rs+bb.ls);
			return rtn;
		}
	}v[1000009];
	long long a[200009];
	void build(int rt,int l,int r){
		if(l==r){
			v[rt].ls=v[rt].rs=v[rt].ss=v[rt].mx=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(rt<<1,l,mid);
		build(rt<<1|1,mid+1,r);
		v[rt]=v[rt<<1]+v[rt<<1|1];
	}
	void update(int rt,int l,int r,int ll,int yy){
		if(l==r){
			a[ll]=yy;
			v[rt].ls=v[rt].rs=v[rt].ss=v[rt].mx=yy;
			return;
		}
		int mid=(l+r)>>1;
		if(ll<=mid)update(rt<<1,l,mid,ll,yy);
		else update(rt<<1|1,mid+1,r,ll,yy);
		v[rt]=v[rt<<1]+v[rt<<1|1];
	}
	node query(int rt,int l,int r,int ll,int rr){
		if(l>=ll&&r<=rr)return v[rt];
		int mid=(l+r)>>1;
		if(ll<=mid&&rr>mid)return query(rt<<1,l,mid,ll,rr)+query(rt<<1|1,mid+1,r,ll,rr);
		if(ll<=mid)return query(rt<<1,l,mid,ll,rr);
		else return query(rt<<1|1,mid+1,r,ll,rr);
	}
} tr0;
int main(){
	long long n,m,bl[200009],lb[200009],a[200009],op,x,y,ans;
	scanf("%lld%lld%lld",&n,&m,&c);
	num=c;
	bl[0]=0;
	for(int i=1;i<=n;i++){
		scanf("%lld",a+i);
		num++;
		if(num<=c){
			bl[i]=bl[i-1];
			lb[i]=num;
		}
		else{
			bl[i]=bl[i-1]+1;
			lb[i]=1;
			num=1;
		}
	}
	num=bl[n];
	vector<seg1> tr1;
	tr1.resize(num+2);
	for(int i=1;i<=num;i++){
		tr1[i].a.resize(c+2);
		tr1[i].b.resize(c+2);
		tr1[i].g.resize(c+2);
		tr1[i].f.resize(c+2);
		tr1[i].fl.resize((c+2)<<1);
		tr1[i].lazyf.resize((c+2)<<1);
		tr1[i].lazyg.resize((c+2)<<1);
		tr1[i].v.resize((c+2)<<1);
	}
	tr2.a.resize(num+2);
	tr2.v.resize((num+2)<<1);
	tr3.a.resize(num+2);
	tr3.v.resize((num+2)<<1);
	for(int i=1;i<=n;i++){
		tr1[bl[i]].a[lb[i]]=a[i];
		if(bl[i]>1)tr1[bl[i]-1].b[lb[i]]=a[i];
		tr0.a[i]=a[i];
	}
	tr0.build(1,1,n);
	for(int i=1;i<=num;i++){
//		cout<<i<<endl;
		tr1[i].bbuild();
//		cout<<i<<endl;
		tr2.a[bl[i]]=tr0.query(1,1,n,bl[i]*c-c+1,bl[i]*c).mx;
//		cout<<i<<endl;
		tr3.a[bl[i]]=tr1[i].v[1].ans;
//		cout<<i<<endl;
	}
	tr2.build(1,1,num);
	tr3.build(1,1,num); 
	for(int i=1;i<=m;i++){
		scanf("%lld",&op);
		if(op==1){
			scanf("%lld%lld",&x,&y);
			tr0.update(1,1,n,x,y);
			tr1[bl[x]].change1(lb[x],y);
			if(bl[x]>1)tr1[bl[x]-1].change2(lb[x],y);
			tr2.change(bl[x],tr0.query(1,1,n,bl[x]*c-c+1,bl[x]*c).mx);
			if(bl[x]>1)tr3.change(bl[x]-1,tr1[bl[x]-1].v[1].ans);
			tr3.change(bl[x],tr1[bl[x]].v[1].ans);
		}
		else{
			scanf("%lld%lld",&x,&y);
			if(y-x+1<=c){
				printf("%lld\n",max(tr0.query(1,1,n,x,y).mx,0ll));
			}
			else if(bl[y]==bl[x]+1){
				ans=tr1[bl[x]].Query3(lb[x],lb[y]);
				ans=max(ans,tr0.query(1,1,n,x,x+c-1).mx);
				ans=max(ans,tr0.query(1,1,n,y-c+1,y).mx);
//				cout<<tr0.query(1,1,n,x,x+c-1).mx<<" "<<tr0.query(1,1,n,y-c+1,y).mx<<endl;
				printf("%lld\n",max(ans,0ll)); 
			}
			else if(bl[y]==bl[x]+2){
				ans=max(tr1[bl[x]].Query1(lb[x]),tr1[bl[y]-1].Query2(lb[y]));
				ans=max(ans,tr2.a[bl[x]+1]);
				ans=max(ans,tr0.query(1,1,n,x,x+c-1).mx);
				ans=max(ans,tr0.query(1,1,n,y-c+1,y).mx);
				printf("%lld\n",max(ans,0ll));
			}
			else{
				ans=max(tr1[bl[x]].Query1(lb[x]),tr1[bl[y]-1].Query2(lb[y]));
				ans=max(ans,tr2.query(1,1,num,bl[x]+1,bl[y]-1));
				ans=max(ans,tr3.query(1,1,num,bl[x]+1,bl[y]-2));
				ans=max(ans,tr0.query(1,1,n,x,x+c-1).mx);
				ans=max(ans,tr0.query(1,1,n,y-c+1,y).mx);
				printf("%lld\n",max(ans,0ll));
			}
		}
	}
	return 0;
}