#include<bits/stdc++.h>
#define int long long
#define INF 114514114514114514ll
#define N 400005
#define ls (x<<1)
#define rs (ls|1)
#define mid ((l+r)>>1)
using namespace std;
int n,m,c,a[N];
namespace s1{
	struct I{
		int s,lx,rx,mx;
		I(int _s=0,int _lx=0,int _rx=0,int _mx=0){
			s=_s,lx=_lx,rx=_rx,mx=_mx;
		}
	}I0;
	I operator+(const I L,const I R){
		return I( 
			L.s+R.s,
			max(L.lx,L.s+R.lx),
			max(R.rx,R.s+L.rx),
			max({L.mx,R.mx,L.rx+R.lx})
		);
	}
	struct S{int l,r;I f;}tr[N<<2];
	void pu(int x){
		tr[x].f=tr[ls].f+tr[rs].f;
	}
	void bd(int x,int l,int r){
		tr[x]=(S){l,r,I0}; 
		if(l==r)return;
		bd(ls,l,mid);
		bd(rs,mid+1,r);
		pu(x);
	}
	void ud(int x,int p,int v){
		if(tr[x].l==tr[x].r){
			tr[x]=(S){p,p,I(v,v,v,v)};
			return;
		}
		if(p<=tr[ls].r)ud(ls,p,v);
		else ud(rs,p,v); 
		pu(x);
	}
	I qr(int x,int l,int r){
		if(l<=tr[x].l&&tr[x].r<=r)return tr[x].f;
		if(r<tr[rs].l)return qr(ls,l,r);
		if(l>tr[ls].r)return qr(rs,l,r);
		return qr(ls,l,r)+qr(rs,l,r);
	}
	void upd(int p,int v){ud(1,p,max(v,0ll));}
	int qry(int l,int r){return qr(1,l,r).mx;}
}
namespace s2{
	struct I{
		int ax,bx,mx;
		I(int _ax=0,int _bx=0,int _mx=0){
			ax=_ax,bx=_bx,mx=_mx;
		}
	}I0(0,0,-INF);
	I operator+(const I L,const I R){
		return I(
			max(L.ax,R.ax),
			max(R.bx,L.bx),
			max({L.mx,R.mx,L.bx+R.ax})
		);
	}
	struct T{
		int at,bt;
		T(int _at=0,int _bt=0){
			at=_at,bt=_bt;
		}
	}T0;
	T operator+(const T L,const T R){
		return T(
			L.at+R.at,
			L.bt+R.bt
		);
	}
	I operator+(const I L,const T R){
		return I(
			L.ax+R.at,
			L.bx+R.bt,
			L.mx+R.at+R.bt
		);
	}
	struct S{int l,r;I f;T t;}tr[N<<2];
	void pu(int x){
		tr[x].f=tr[ls].f+tr[rs].f;
	}
	void pt(int x,T t){
		tr[x].f=tr[x].f+t;
		tr[x].t=tr[x].t+t;
	}
	void pd(int x){
		if(tr[x].t.at||tr[x].t.bt){
			pt(ls,tr[x].t),pt(rs,tr[x].t);
			tr[x].t=T0;
		}
	}
	void bd(int x,int l,int r){
		tr[x]=(S){l,r,I0,T0};
		if(l==r)return;
		bd(ls,l,mid);
		bd(rs,mid+1,r);
		pu(x);
	}
	void ud(int x,int l,int r,T t){
		if(l<=tr[x].l&&tr[x].r<=r){
			return pt(x,t);
		}
		pd(x);
		if(l<=tr[ls].r)ud(ls,l,r,t);
		if(tr[rs].l<=r)ud(rs,l,r,t);
		pu(x);
	}
	I qr(int x,int l,int r){
		if(l<=tr[x].l&&tr[x].r<=r)return tr[x].f;
		pd(x);
		if(r<tr[rs].l)return qr(ls,l,r);
		if(l>tr[ls].r)return qr(rs,l,r);
		return qr(ls,l,r)+qr(rs,l,r);
	}
	void upd(int p,int v){
		if(p+c<=n){
			int q=(p-1)/c*c+1;
			ud(1,q,p,T(v,0));
		}
		if(p-c>=1){
			int q=(p-1)/c*c;
			ud(1,p-c,q,T(0,v));
		}
	}
	int qry(int l,int r){
		return qr(1,l,r).mx;}
}
namespace s3{
	struct I{
		int mx;
		I(int _mx=0){
			mx=_mx;
		}
	}I0;
	I operator+(const I L,const I R){
		return I(
			max(L.mx,R.mx)
		);
	}
	struct S{int l,r;I f;}tr[N<<2];
	void pu(int x){
		tr[x].f=tr[ls].f+tr[rs].f;
	}
	void bd(int x,int l,int r){
		tr[x]=(S){l,r,I0}; 
		if(l==r)return;
		bd(ls,l,mid);
		bd(rs,mid+1,r);
		pu(x);
	}
	void ud(int x,int p,int v){
		if(tr[x].l==tr[x].r){
			tr[x]=(S){p,p,I(v)};
			return;
		}
		if(p<=tr[ls].r)ud(ls,p,v);
		else ud(rs,p,v);
		pu(x);
	}
	I qr(int x,int l,int r){
		if(l<=tr[x].l&&tr[x].r<=r)return tr[x].f;
		if(r<tr[rs].l)return qr(ls,l,r);
		if(l>tr[ls].r)return qr(rs,l,r);
		return qr(ls,l,r)+qr(rs,l,r);
	}
	void upd(int p,int v){ud(1,p,v);}
	int qry(int l,int r){return qr(1,l,r).mx;}
}
void init(){
	s1::bd(1,1,n);
	s2::bd(1,1,n-c);
	s3::bd(1,1,n/c-1);
}
void update(int p,int v){
	s1::upd(p,v);
	s2::upd(p,v-a[p]);
	int bp=(p-1)/c+1;
	s3::upd(bp,
	max(s1::qry((bp-1)*c+1,bp*c),
		s2::qry((bp-1)*c+1,bp*c)));
	a[p]=v;
}
int query(int l,int r){
	int bl=(l-1)/c+1,br=(r-1)/c+1;
	if(r-l+1<=c)return s1::qry(l,r);
	int ans=max({
		s1::qry(l,l+c-1),
		s1::qry(r-c+1,r),
		s2::qry(l,bl*c),
		s2::qry(r-c,br*c-c)});
	if(bl+1<br-1)ans=max(ans,s3::qry(bl+1,br-2));
	if(bl+1<=br-1)ans=max(ans,s1::qry((br-2)*c+1,(br-1)*c));
	return ans;
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m>>c;int nn=n;n=(n+2*c-1)/c*c;
	init();
	for(int i=1,x;i<=nn;i++)cin>>x,update(i,x);
	for(int i=1,op,x,y;i<=m;i++){
		cin>>op>>x>>y;
//			if(c==5)cout<<x<<' '<<y<<'\n';
		if(op==1)update(x,y);
		else{
			cout<<query(x,y)<<'\n';
		}
	}
	return 0;
}