#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
typedef long long ll;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin)),p1==p2)?EOF:*p1++
template<class rd>
void read(rd &x){
	char c=getchar();int f=1;
	for(;c!='-'&&(c<48||c>57);c=getchar());
	if(c=='-')f=-f,c=getchar();
	for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
int n,m,B,pn,a[N],pos[N],pl[N],pr[N];
ll sl[N],sr[N];
#define L k<<1
#define R k<<1|1
struct node{
	ll lmx,rmx,mx,sum;
}tr[N<<2];
inline node operator +(node a,node b){
	node c;
	c.sum=a.sum+b.sum;
	c.lmx=max(a.lmx,a.sum+b.lmx);
	c.rmx=max(b.rmx,b.sum+a.rmx);
	c.mx=max(max(a.mx,b.mx),a.rmx+b.lmx);
	return c;
}
struct seg1{
	node tr[N<<2];
	void build(int k,int l,int r){
		if(l==r){
			tr[k].mx=tr[k].lmx=tr[k].rmx=tr[k].sum=a[l];
			return;
		}
		int mid=l+r>>1;
		build(L,l,mid),build(R,mid+1,r);
		if(pos[l]==pos[r])tr[k]=tr[L]+tr[R];
	}
	void modify(int k,int l,int r,int x,int v){
		if(l==r){
			tr[k].mx=tr[k].lmx=tr[k].rmx=tr[k].sum=v;
			return;
		}
		int mid=l+r>>1;
		if(x<=mid)modify(L,l,mid,x,v);
		else modify(R,mid+1,r,x,v);
		if(pos[l]==pos[r])tr[k]=tr[L]+tr[R];
	}
	node query(int k,int l,int r,int x,int y){
		if(x<=l&&r<=y)return tr[k];
		int mid=l+r>>1;
		if(x<=mid&&y>mid)return query(L,l,mid,x,y)+query(R,mid+1,r,x,y);
		if(x<=mid)return query(L,l,mid,x,y);
		else return query(R,mid+1,r,x,y);
	}
}T1;
struct seg2{
	ll mx[N<<2];
	void build(int k,int l,int r){
		if(l==r){
			ll s=0;
			for(int i=pl[l];i<=pr[l];++i){
				s=max(0ll,s+a[i]);
				mx[k]=max(mx[k],s);
			}
			return;
		}
		int mid=l+r>>1;
		build(L,l,mid),build(R,mid+1,r);
		mx[k]=max(mx[L],mx[R]);
	}
	void modify(int k,int l,int r,int x,int v){
		if(l==r)return mx[k]=v,void();
		int mid=l+r>>1;
		if(x<=mid)modify(L,l,mid,x,v);
		else modify(R,mid+1,r,x,v);
		mx[k]=max(mx[L],mx[R]);
	}
	ll query(int k,int l,int r,int x,int y){
		if(x<=l&&r<=y)return mx[k];
		int mid=l+r>>1;ll res=0;
		if(x<=mid)res=max(res,query(L,l,mid,x,y));
		if(y>mid)res=max(res,query(R,mid+1,r,x,y));
		return res;
	}
}T2;
struct seg3{
	ll *s1,*s2,*tg,*m1,*m2;
	inline void pushup(int k){
		s2[k]=s2[L]+s2[R];
		s1[k]=max(s1[L],s1[R]);
		m2[k]=max(m2[L],s2[L]+m2[R]);
		m1[k]=max(m1[L],max(m1[R]+s2[L],s1[R]+m2[L]));
	}
	inline void pushtg(int k,ll v){
		tg[k]+=v,s1[k]+=v,m1[k]+=v;
	}
	inline void pushdown(int k){
		if(tg[k]){
			pushtg(L,tg[k]);
			pushtg(R,tg[k]);
			tg[k]=0;
		}
	}
	void build(int k,int l,int r){
		tg[k]=0;
		if(l==r){
			s2[k]=sr[l],m2[k]=max(0ll,s2[k]),s1[k]=m1[k]=sl[l];
			return;
		}
		int mid=l+r>>1;
		build(L,l,mid),build(R,mid+1,r);
		pushup(k);
	}
#define New new ll [B<<2]
	void init(int x){
		s1=New,s2=New,tg=New,m1=New,m2=New;
		for(int i=1;i<=B;++i){
			sr[i]=a[pl[x+1]+i-1];
			sl[i]=a[pl[x]+i-1];
		}
		for(int i=B;i;--i)sl[i]+=sl[i+1];
		build(1,1,B);
	}
	void modify(int k,int l,int r,int x,ll v){
		if(x>=r)return pushtg(k,v);
		int mid=l+r>>1;
		pushdown(k);
		if(x>mid)modify(R,mid+1,r,x,v);
		modify(L,l,mid,x,v);
		pushup(k);
	}
	void modify2(int k,int l,int r,int x,int v){
		if(l==r)return s2[k]=v,m2[k]=max(0ll,s2[k]),void();
		int mid=l+r>>1;
		pushdown(k);
		if(x<=mid)modify2(L,l,mid,x,v);
		else modify2(R,mid+1,r,x,v);
		pushup(k);
	}
	ll query(int k,int l,int r,int x,ll s,ll mx){
		if(x<=l)return max(mx+s1[k],s+m1[k]);
		int mid=l+r>>1;
		pushdown(k);
		if(x<=mid)return max(query(L,l,mid,x,s,mx),query(R,mid+1,r,x,s+s2[L],max(mx,s+m2[L])));
		return query(R,mid+1,r,x,s+s2[L],max(mx,s+m2[L]));
	}
}T3[N],T4[N];
void Modify(int x,int y){
	int lx=pos[x];
	T1.modify(1,1,n,x,y);
	T2.modify(1,1,pn,lx,T1.query(1,1,n,pl[lx],pr[lx]).mx);
	if(lx<pn){
		T3[lx].modify(1,1,B,x-pl[lx]+1,y-a[x]);
		T4[pn-lx].modify2(1,1,B,pr[lx]-x+1,y);
	}
	if(lx>1){
		T3[lx-1].modify2(1,1,B,x-pl[lx]+1,y);
		T4[pn-lx+1].modify(1,1,B,pr[lx]-x+1,y-a[x]);
	}
	a[x]=y;
}
ll Query(int l,int r){
	if(r-l+1<=B)return max(0ll,T1.query(1,1,n,l,r).mx);
	int lx=pos[l],rx=pos[r];
	if(l==pl[lx])--lx;
	if(r==pr[rx])++rx;
	ll res=0;
	if(lx+1<rx)res=max(res,T2.query(1,1,pn,lx+1,rx-1));
	if(lx==pos[l])res=max(res,T3[lx].query(1,1,B,l-pl[lx]+1,0,0));
	if(rx==pos[r])res=max(res,T4[pn-rx+1].query(1,1,B,pr[rx]-r+1,0,0));
	return res;
}
int main(){
	read(n),read(m),read(B);
	for(int i=1;i<=n;++i)read(a[i]),pos[i]=(i-1)/B+1;
	pn=pos[n];
	while(n%B!=0)++n,pos[n]=pn;
	for(int i=1;i<=pn;++i)pl[i]=(i-1)*B+1,pr[i]=i*B;
	T1.build(1,1,n),T2.build(1,1,pn);
	for(int i=1;i<pos[n];++i)T3[i].init(i);
	reverse(a+1,a+n+1);
	for(int i=1;i<pos[n];++i)T4[i].init(i);
	reverse(a+1,a+n+1);
	for(int i=1,op,x,y;i<=m;++i){
		read(op),read(x),read(y);
		if(op==1)Modify(x,y);
		else printf("%lld\n",Query(x,y));
	}
	return 0;
}