#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REPG(i,h,x) for(int i=h[x];~i;i=edge[i].next)
#define CLR(a,x) memset(a,x,sizeof(a))
#define pii pair<int,int>
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;

const int N=1e6+5;
int n,q,K,bcnt,a[N<<1],st[N],ed[N],bel[N<<1];
ll c[N],d[N],pre[N<<1],suf[N<<1];
struct node{ll pre,suf,sum,mx;};
struct node2{ll v1,v2,mx;};
inline int lc(int p){return p<<1;}
inline int rc(int p){return p<<1|1;}
struct SGT1{
	vector<node> t;
	inline void init(int n){t.resize(n*4);}
	inline node merge(node l,node r){
		node ret;
		ret.sum=l.sum+r.sum;
		ret.pre=max(l.pre,l.sum+r.pre);
		ret.suf=max(r.suf,l.suf+r.sum);
		ret.mx=max(max(l.mx,r.mx),l.suf+r.pre);
		return ret;
	}
	inline void pushup(int p){t[p]=merge(t[lc(p)],t[rc(p)]);}
	void update(int tt,int l,int r,int p,int c){
		if(l==r) return (void)(t[p]={max(c,0),max(c,0),c,max(c,0)});
		int mid=l+r>>1;
		if(tt<=mid) update(tt,l,mid,lc(p),c);
		else update(tt,mid+1,r,rc(p),c);
		pushup(p);
	}
	node query(int tl,int tr,int l,int r,int p){
		if(tl<=l&&r<=tr) return t[p];
		int mid=l+r>>1;
		if(tl>mid) return query(tl,tr,mid+1,r,rc(p));
		else if(tr<=mid) return query(tl,tr,l,mid,lc(p));
		return merge(query(tl,tr,l,mid,lc(p)),query(tl,tr,mid+1,r,rc(p)));
	}
	void build(int p,int l,int r,int a[]){
		if(l==r) return (void)(t[p]={max(a[l],0),max(a[l],0),a[l],max(a[l],0)});
		int mid=l+r>>1;
		build(lc(p),l,mid,a),build(rc(p),mid+1,r,a);
		pushup(p);
	}
}t1[N],t5;
struct SGT2{
	vector<node2> t;
	vector<ll> lazy1,lazy2;
	inline void init(int n){t.resize(n*4),lazy1.resize(n*4),lazy2.resize(n*4);}
	inline node2 merge(node2 l,node2 r){
		node2 ret;
		ret.v1=max(l.v1,r.v1),ret.v2=max(l.v2,r.v2);
		ret.mx=max(max(l.mx,r.mx),l.v1+r.v2);
		return ret;
	}
	inline void pushup(int p){t[p]=merge(t[lc(p)],t[rc(p)]);}
	inline void push(int p,ll v1,ll v2){t[p].v1+=v1,t[p].v2+=v2,t[p].mx+=v1+v2,lazy1[p]+=v1,lazy2[p]+=v2;}
	inline void pushdown(int p){if(lazy1[p]||lazy2[p]) push(lc(p),lazy1[p],lazy2[p]),push(rc(p),lazy1[p],lazy2[p]),lazy1[p]=lazy2[p]=0;}
	void update(int tl,int tr,int l,int r,int p,ll v1,ll v2){
		if(tl<=l&&r<=tr) return push(p,v1,v2);
		int mid=l+r>>1;
		pushdown(p);
		if(tl<=mid) update(tl,tr,l,mid,lc(p),v1,v2);
		if(tr>mid) update(tl,tr,mid+1,r,rc(p),v1,v2);
		pushup(p);
	}
	node2 query(int tl,int tr,int l,int r,int p){
		if(tl<=l&&r<=tr) return t[p];
		int mid=l+r>>1;
		if(tl>mid) return query(tl,tr,mid+1,r,rc(p));
		else if(tr<=mid) return query(tl,tr,l,mid,lc(p));
		return merge(query(tl,tr,l,mid,lc(p)),query(tl,tr,mid+1,r,rc(p)));
	}
	void build(int p,int l,int r,ll a[],ll b[]){
		if(l==r) return (void)(t[p]={a[l],b[l],-LLINF});//v1:pre v2:suf
		int mid=l+r>>1;
		build(lc(p),l,mid,a,b),build(rc(p),mid+1,r,a,b);
		pushup(p);
	}	
}t2[N];
struct SGT3{
	ll t[N<<2];
	inline void pushup(int p){t[p]=max(t[lc(p)],t[rc(p)]);}
	void update(int tt,int l,int r,int p,ll c){
		if(l==r) return (void)(t[p]=c);
		int mid=l+r>>1;
		if(tt<=mid) update(tt,l,mid,lc(p),c);
		else update(tt,mid+1,r,rc(p),c);
		pushup(p);
	}
	ll query(int tl,int tr,int l,int r,int p){
		if(tl<=l&&r<=tr) return t[p];
		int mid=l+r>>1;ll ret=-LLINF;
		if(tl<=mid) ret=query(tl,tr,l,mid,lc(p));
		if(tr>mid) ret=max(ret,query(tl,tr,mid+1,r,rc(p)));
		return ret;
	}	
	void build(int p,int l,int r,ll a[]){
		if(l==r) return (void)(t[p]=a[l]);
		int mid=l+r>>1;
		build(lc(p),l,mid,a),build(rc(p),mid+1,r,a);
		pushup(p);
	}
}t3,t4;
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d%d%d",&n,&q,&K);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	t5.init(n),t5.build(1,1,n,a);
	bcnt=(n+K-1)/K+1;
	for(int i=1;i<=bcnt;i++){
		st[i]=(i-1)*K+1,ed[i]=(i==bcnt?n+K:i*K);
		for(int j=st[i];j<=ed[i];j++) bel[j]=i;
		printf("%d %d\n",st[i],ed[i]);
		t1[i].init(K),t1[i].build(1,1,K,a+st[i]-1);
		c[i]=t1[i].t[1].mx;
		if(i==1) continue;
		for(int j=1;j<=K;j++) pre[j]=pre[j-1]+a[j+st[i]-1];
		for(int j=K;j>=1;j--) suf[j]=suf[j+1]+a[j+st[i]-1-K];
		t2[i].init(K),t2[i].build(1,1,K,pre,suf);
		d[i]=t2[i].t[1].mx;	
	}
	t3.build(1,1,bcnt,c),t4.build(1,1,bcnt,d);
	while(q--){
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op==1){
			t5.update(x,1,n,1,y);
			t1[bel[x]].update(x-st[bel[x]]+1,1,K,1,y),t3.update(bel[x],1,bcnt,1,t1[bel[x]].t[1].mx);
			if(bel[x]>1) t2[bel[x]].update(x-st[bel[x]]+1,K,1,K,1,y-a[x],0),t4.update(bel[x],1,bcnt,1,t2[bel[x]].t[1].mx);
			if(bel[x]<bcnt) t2[bel[x]+1].update(x-st[bel[x]]+1,K,1,K,1,0,y-a[x]),t4.update(bel[x]+1,1,bcnt,1,t2[bel[x]+1].t[1].mx);
			a[x]=y;
		}
		if(op==2){
			if(bel[x]==bel[y]){printf("%lld\n",t5.query(x,y,1,n,1).mx);continue;}
			ll ans=0;
			ans=max(ans,max(t5.query(x,x+K-1,1,n,1).mx,t5.query(y-K+1,y,1,n,1).mx));
			if(bel[x]+1==bel[y]) ans=max(ans,t2[bel[y]].query(x-st[bel[x]]+1,y-st[bel[y]]+1,1,K,1).mx);
			else{
				ans=max(ans,t3.query(bel[x]+1,bel[y]-1,1,bcnt,1));
				ans=max(ans,max(t2[bel[x]+1].query(x-st[bel[x]]+1,K,1,K,1).mx,t2[bel[y]].query(1,y-st[bel[y]]+1,1,K,1).mx));
				if(bel[x]+2<=bel[y]) ans=max(ans,t4.query(bel[x]+2,bel[y]-1,1,bcnt,1));
			}
			printf("%lld\n",ans);
		}	
	}
	return 0;
}