#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid (l+r>>1)
const int N=5e5+99;
int n,m,q,c,a[N];
int L[N],R[N],bel[N];
int st[N],ed[N];
struct SGT1{//鏈€澶у瓙娈靛拰
	int rt[N],cntnode;
	struct tree{
		int ln,rn;
		int lmx,rmx,mx,sum;
		tree(){ ln=rn=0; }
	}tr[N<<2];
	SGT1(){ memset(rt,0,sizeof(rt)); cntnode=0; }
	void pushup(int node){ 
		tr[node].lmx=max(tr[tr[node].ln].lmx,tr[tr[node].ln].sum+tr[tr[node].rn].lmx);
		tr[node].rmx=max(tr[tr[node].rn].rmx,tr[tr[node].rn].sum+tr[tr[node].ln].rmx);
		tr[node].mx=max(max(tr[tr[node].ln].mx,tr[tr[node].rn].mx),tr[tr[node].ln].rmx+tr[tr[node].rn].lmx);
		tr[node].sum=tr[tr[node].ln].sum+tr[tr[node].rn].sum;
		return;
	}
	void build(int &node,int l,int r){
		if(!node) node=++cntnode;
		if(l==r){ tr[node].lmx=tr[node].rmx=tr[node].mx=max(a[l],0ll); tr[node].sum=a[l]; return; }
		build(tr[node].ln,l,mid); build(tr[node].rn,mid+1,r);
		pushup(node);
		return;
	}
	void change(int node,int l,int r,int tar){
		if(l==r){ tr[node].lmx=tr[node].rmx=tr[node].mx=max(a[l],0ll); tr[node].sum=a[l]; return; }
		if(tar<=mid) change(tr[node].ln,l,mid,tar);
		else change(tr[node].rn,mid+1,r,tar);
		pushup(node);
		return;
	}
	int cnt;
	tree ab[100],now,ans;
	void query(int node,int l,int r,int tarl,int tarr){
		if(tarl<=l&&r<=tarr){ ab[++cnt]=tr[node]; return; }
		if(tarl<=mid) query(tr[node].ln,l,mid,tarl,tarr);
		if(tarr>mid) query(tr[node].rn,mid+1,r,tarl,tarr);
		return;
	}
	int query(int l,int r){
		cnt=0;
		query(1,1,n,l,r);
		ans=ab[1];
		for(int i=2;i<=cnt;i++){
			now=ans;
			ans.lmx=max(now.lmx,now.sum+ab[i].lmx);
			ans.rmx=max(ab[i].rmx,ab[i].sum+now.rmx);
			ans.mx=max(max(now.mx,ab[i].mx),now.rmx+ab[i].lmx);
			ans.sum=now.sum+ab[i].sum;
		}
		return ans.mx;
	}
}SA,SP;
int apre[N],abac[N];
struct SGT3{//鍓嶅悗娈垫嫾鎺?
	int rt[N],cntnode;
	SGT3(){ memset(rt,0,sizeof(rt)); cntnode=0; }
	struct tree{
		int ln,rn;
		int pmx,bmx,ans;
		int tagp,tagb;
		tree(){ ln=rn=tagp=tagb=0; }
	}tr[N<<2];
	void pushto(int node,int tp,int tb){
		tr[node].pmx+=tp; tr[node].bmx+=tb;
		tr[node].tagp+=tp; tr[node].tagb+=tb;
		tr[node].ans+=tp+tb;
	}
	void pushdown(int node){
		if(!tr[node].tagp&&!tr[node].tagb) return;
		pushto(tr[node].ln,tr[node].tagp,tr[node].tagb);
		pushto(tr[node].rn,tr[node].tagp,tr[node].tagb);
		tr[node].tagp=tr[node].tagb=0;
		return;
	}
	void pushup(int node){
		tr[node].pmx=max(tr[tr[node].ln].pmx,tr[tr[node].rn].pmx);
		tr[node].bmx=max(tr[tr[node].ln].bmx,tr[tr[node].rn].bmx);
		tr[node].ans=max(max(tr[tr[node].ln].ans,tr[tr[node].rn].ans),tr[tr[node].ln].pmx+tr[tr[node].rn].bmx);
		return;
	}
	void build(int &node,int l,int r){
		if(!node) node=++cntnode;
		if(l==r){ tr[node].pmx=apre[l]; tr[node].bmx=abac[l]; tr[node].ans=-1e17; return; }
		build(tr[node].ln,l,mid); build(tr[node].rn,mid+1,r);
		pushup(node);
		return;
	}
	void change(int node,int l,int r,int tarl,int tarr,int val,int tp){
		// 0 for pre ; 1 for bac
		if(tarl<=l&&r<=tarr){
			if(tp==0) tr[node].pmx+=val,tr[node].tagp+=val,tr[node].ans+=val;
			else tr[node].bmx+=val,tr[node].tagb+=val,tr[node].ans+=val;
			return;
		}
		pushdown(node);
		if(tarl<=mid) change(tr[node].ln,l,mid,tarl,tarr,val,tp);
		if(tarr>mid) change(tr[node].rn,mid+1,r,tarl,tarr,val,tp);
		pushup(node);
		return;
	}
	int query(int node,int l,int r,int tarl,int tarr){
		if(tarl<=l&&r<=tarr) return tr[node].ans;
		pushdown(node);
		if(tarr<=mid) return query(tr[node].ln,l,mid,tarl,tarr);
		if(tarl>mid) return query(tr[node].rn,mid+1,r,tarl,tarr);
		return max(query(tr[node].ln,l,mid,tarl,tarr),query(tr[node].rn,mid+1,r,tarl,tarr));
	}
}S;

#define ln node<<1
#define rn node<<1|1
int MX[2][N];
//0 鏁存 锛? 鍓嶅悗娈?
struct SGT2{//鏈€澶у瓙娈靛拰鏈€鍊?
	int mx[N<<2];
	SGT2(){ memset(mx,0,sizeof(mx)); }
	void build(int node,int l,int r,int tp){
		if(l==r){ mx[node]=MX[tp][l]; return; }
		build(ln,l,mid,tp); build(rn,mid+1,r,tp);
		mx[node]=max(mx[ln],mx[rn]);
		return;
	}
	void change(int node,int l,int r,int tar,int tp){
		if(l==r){ mx[node]=MX[tp][l]; return; }
		if(tar<=mid) change(ln,l,mid,tar,tp);
		else change(rn,mid+1,r,tar,tp);
		mx[node]=max(mx[ln],mx[rn]);
		return;
	}
	int query(int node,int l,int r,int tarl,int tarr){
		if(tarl<=l&&r<=tarr) return mx[node];
		int re=0;
		if(tarl<=mid) re=max(re,query(ln,l,mid,tarl,tarr));
		if(tarr>mid) re=max(re,query(rn,mid+1,r,tarl,tarr));
		return re;
	}
}sgt0,sgt1;
void init(){
	for(int i=1;i<=n;i++){
		L[i]=(i-1)/c*c+1;
		R[i]=L[i]+c-1;
		bel[i]=(i-1)/c+1;
	}
	SA.build(SA.rt[1],1,n);
	for(int i=1;i<=n/c;i++)
		SP.build(SP.rt[i],st[i]=i*c-c+1,ed[i]=i*c);
	for(int i=1;i<=m;i++){
		apre[st[i]]=a[st[i]];
		for(int j=st[i]+1;j<=ed[i];j++)
			apre[j]=apre[j-1]+a[j];
		S.build(S.rt[i],st[i],ed[i]);
		if(i==m) continue;
		abac[c+ed[i]]=a[ed[i]];
		for(int j=ed[i]-1;j>=st[i];j--)
			abac[c+j]=abac[c+j+1]+a[j];
	}
	for(int i=1;i<=m;i++)
		MX[0][i]=SP.tr[SP.rt[i]].mx,MX[1][i]=S.tr[S.rt[i]].ans;
	sgt0.build(1,1,m,0); sgt1.build(1,1,m,1);
	return;
}
void change(int x,int delta){
	S.change(S.rt[bel[x]],L[x],R[x],x,R[x],delta,0);
	MX[1][bel[x]]=S.tr[S.rt[bel[x]]].ans;
	sgt1.change(1,1,m,bel[x],1);
	if(bel[x]!=m){
		S.change(S.rt[bel[x]+1],L[x+c],R[x+c],L[x+c],x+c,delta,1);
		MX[1][bel[x]+1]=S.tr[S.rt[bel[x]+1]].ans;
		sgt1.change(1,1,m,bel[x]+1,1);
	}
	return;
}
void update(int x){
	SA.change(1,1,n,x);
	SP.change(SP.rt[bel[x]],st[bel[x]],ed[bel[x]],x);
	MX[0][bel[x]]=SP.tr[SP.rt[bel[x]]].mx;
	sgt0.change(1,1,m,bel[x],0);
	return;
}
int cnt;
void solve(int l,int r){
	int ans=0;
	if(r-l+1<=c) ans=max(ans,SA.query(l,r));
	else if(bel[l]+1==bel[r]){
		ans=max(ans,SA.query(l,l+c-1));
		ans=max(ans,SA.query(r-c+1,r));
		ans=max(ans,S.query(S.rt[bel[r]],L[r],R[r],l+c,r));
	}
	else{
		ans=max(ans,SA.query(l,l+c-1));
		ans=max(ans,SA.query(r-c+1,r));
		ans=max(ans,sgt0.query(1,1,m,bel[l]+1,bel[r]-1));
		if(bel[l]+1!=bel[r]-1)
			ans=max(ans,sgt1.query(1,1,m,bel[l]+2,bel[r]-1));
		ans=max(ans,S.query(S.rt[bel[r]],L[r],R[r],L[r],r));
		ans=max(ans,S.query(S.rt[bel[l]+1],L[l+c],R[l+c],l+c,R[l+c]));
	}
	if(c==5){
		cnt++;
		if(cnt==6288) cout<<l<<" "<<r<<endl;
		return;
	}
	cout<<ans<<'\n';
	return;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>q>>c;
	for(int i=1;i<=n;i++) cin>>a[i];
	n=((n-1)/c+1)*c; m=n/c;
	init();
	int tp,x,y,l,r;
	while(q--){
		cin>>tp;
//		cout<<tp<<endl;
		if(tp==1){
			cin>>x>>y;
			change(x,y-a[x]);
			a[x]=y; update(x);
		}
		else{
			cin>>l>>r;
			solve(l,r);
		}
	}
	return 0;
}