#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
ll mx[800005],tg[800005],lp[800005],lsum[800005],rp[800005],rsum[800005],mx2[800005];
ll mxs[800005],tg2[800005],mxx[800005],num[800005];
ll ans=0;
int n,m,c,gl,gr;
ll a[200005],sum[200005];
ll ty,x,y,v;
ll tr[200005];
const ll inf=1e18;
vector<int>q;
int lowbit(int p){return p&-p;}
void update(int p,int val)//单点更新
{
    while(p<=n){
        tr[p]+=val;
        p+=lowbit(p);//由叶子节点向上更新树状数组C，从左往右更新
    }
}
ll asksum(int p)//求区间[1,i]内所有元素的和
{
    ll ret=0;
    while(p>0){
        ret+=tr[p];//从右往左累加求和
        p-=lowbit(p);
    }
    return ret;
}
void build(int p,int l,int r)
{
	num[p]=r-l+1;
	if(l==r)
	{
		mx[p]=sum[min(n,l+c-1)]-sum[l-1];
		mxs[p]=sum[l];tg2[p]=0;
		mxx[p]=sum[l];
		tg[p]=0;
		if(a[l]>=0)lp[p]=rp[p]=1,lsum[p]=rsum[p]=a[l];
		else lp[p]=rp[p]=lsum[p]=rsum[p]=0;
		mx2[p]=lsum[p];
		return;
	}
	int mid=(l+r)/2;
	build(2*p,l,mid);
	build(2*p+1,mid+1,r);
	mx[p]=max(mx[2*p],mx[2*p+1]);
	tg[p]=0;
	mxs[p]=min(mxs[2*p],mxs[2*p+1]);
	mxx[p]=max(mxx[2*p],mxx[2*p+1]);
	tg2[p]=0;
	if(lp[2*p]==mid-l+1)
	{
		lp[p]=lp[2*p]+lp[2*p+1];
		lsum[p]=lsum[2*p]+lsum[2*p+1];
	}
	else
	{
		lp[p]=lp[2*p];
		lsum[p]=lsum[2*p];
	}
	if(rp[2*p+1]==r-mid)
	{
		rp[p]=rp[2*p+1]+rp[2*p];
		rsum[p]=rsum[2*p+1]+rsum[2*p];
	}
	else
	{
		rp[p]=rp[2*p+1];
		rsum[p]=rsum[2*p+1];
	}
	mx2[p]=max(mx2[2*p],mx2[2*p+1]);
	if(rp[2*p]+lp[2*p+1]<=c)mx2[p]=max(mx2[p],rsum[2*p]+lsum[2*p+1]);
}
void activate(int p,int v)
{
	mx[p]+=v;
	tg[p]+=v;
}
void push(int p)
{
	if(tg[p]==0)return;
	activate(2*p,tg[p]);
	activate(2*p+1,tg[p]);
	tg[p]=0;
}
void activate2(int p,int v)
{
	mxs[p]+=v;
	mxx[p]+=v;
	tg2[p]+=v;
}
void push2(int p)
{
	if(tg2[p]==0)return;
	activate2(2*p,tg2[p]);
	activate2(2*p+1,tg2[p]);
	tg2[p]=0;
}
void modify1(int p,int l,int r)
{
	if(gl>r||gr<l)return;
	if(gl<=l&&gr>=r)
	{
		activate(p,v);
		return;
	}
	push(p);
	int mid=(l+r)/2;
	modify1(2*p,l,mid);
	modify1(2*p+1,mid+1,r);
	mx[p]=max(mx[2*p],mx[2*p+1]);
	
}
void modify3(int p,int l,int r)
{
	if(gl>r||gr<l)return;
		if(gl<=l&&gr>=r)
		{
			activate2(p,v);
			return;
		}
		push2(p);
		int mid=(l+r)/2;
		modify3(2*p,l,mid);
		modify3(2*p+1,mid+1,r);
		mxs[p]=min(mxs[2*p],mxs[2*p+1]);
		mxx[p]=max(mxx[2*p],mxx[2*p+1]);
}
void modify2(int p,int l,int r)
{
	if(l==r)
	{
		if(a[l]>=0)lp[p]=rp[p]=1,lsum[p]=rsum[p]=a[l];
		else lp[p]=rp[p]=lsum[p]=rsum[p]=0;
		mx2[p]=lsum[p];
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid)modify2(2*p,l,mid);
	else modify2(2*p+1,mid+1,r);
		if(lp[2*p]==mid-l+1)
		{
			lp[p]=lp[2*p]+lp[2*p+1];
			lsum[p]=lsum[2*p]+lsum[2*p+1];
		}
		else
		{
			lp[p]=lp[2*p];
			lsum[p]=lsum[2*p];
		}
		if(rp[2*p+1]==r-mid)
		{
			rp[p]=rp[2*p+1]+rp[2*p];
			rsum[p]=rsum[2*p+1]+rsum[2*p];
		}
		else
		{
			rp[p]=rp[2*p+1];
			rsum[p]=rsum[2*p+1];
		}
		mx2[p]=max(mx2[2*p],mx2[2*p+1]);
		if(rp[2*p]+lp[2*p+1]<=c)mx2[p]=max(mx2[p],rsum[2*p]+lsum[2*p+1]);
}
ll ask1(int p,int l,int r)
{
	if(gl>r||gr<l)return -inf;
	if(gl<=l&&gr>=r)return mx[p];
	int mid=(l+r)/2;
	push(p);
	return max(ask1(2*p,l,mid),ask1(2*p+1,mid+1,r));
}
ll ask2(int p,int l,int r)
{
	if(gl>r||gr<l)return inf;
	if(gl<=l&&gr>=r)return mxs[p];
	int mid=(l+r)/2;
	push2(p);
	return min(ask2(2*p,l,mid),ask2(2*p+1,mid+1,r));
}
ll ask3(int p,int l,int r)
{
	if(gl>r||gr<l)return -inf;
	if(gl<=l&&gr>=r)return mxx[p];
	int mid=(l+r)/2;
	push2(p);
	return max(ask3(2*p,l,mid),ask3(2*p+1,mid+1,r));
}
void ask4(int p,int l,int r)
{
	if(gl>r||gr<l)return;
	if(gl<=l&&gr>=r)
	{
		ans=max(ans,mx2[p]);
		q.push_back(p);
		return;
	}
	int mid=(l+r)/2;
	ask4(2*p,l,mid);
	ask4(2*p+1,mid+1,r);
}
signed main()
{
	//freopen("233.txt","r",stdin);
	//freopen("outm.txt","w",stdout);
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),update(i,a[i]);
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&ty,&x,&y);
		//printf("%lld %lld %lld\n",ty,x,y);
		if(ty==1)
		{
			gl=max(1ll,x-c+1);
			gr=x;
			v=y-a[x];
			ll tmp=v;
			update(x,v);
			a[x]=y;
			modify1(1,1,n);
			gl=x;gr=n;
			v=tmp;
			modify3(1,1,n);
			modify2(1,1,n);
		}
		else
		{
			ans=0;
			gl=x;gr=y-c+1;
			if(gl<=gr)ans=max(ans,ask1(1,1,n));
			ll sumr=asksum(y);
			ll suml=asksum(x-1);
			gl=max(y-c+1,x-1);gr=y-1;
			if(gl<=gr)
			{
				if(gl>0)ans=max(ans,sumr-ask2(1,1,n));
				else ans=max(ans,sumr-min(0ll,ask2(1,1,n)));
			}
			gl=x;gr=min(x+c-1,y);
			if(gl<=gr)ans=max(ans,ask3(1,1,n)-suml);
			q.clear();
			gl=x;gr=y;
			ask4(1,1,n);
			ll rpp,rs;
			rpp=rp[q[0]];
			rs=rsum[q[0]];
			for(int j=1;j<q.size();j++)
			{
				int id=q[j];
				if(lp[id]+rpp<=c)ans=max(ans,rs+lsum[id]);
				if(rp[id]==num[id])
				{
					rpp=rp[id]+rpp;
					rs=rs+rsum[id];
				}
				else
				{
					rpp=rp[id];
					rs=rsum[id];
				}
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}