#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
typedef long long ll;
int n,q,c,a[N],pr[N],nx[N],id[N];

struct sgt1{
  struct st{
    ll lmx,rmx,mx,sum;
  }t[N<<2];
  void pushup(st &p,st p1,st p2){
    p.sum=p1.sum+p2.sum;
    p.mx=max({p1.mx,p2.mx,p1.rmx+p2.lmx});
    p.lmx=max(p1.lmx,p2.lmx+p1.sum);
    p.rmx=max(p2.rmx,p1.rmx+p2.sum);
  }
  void build(int p,int l,int r){//cout<<p<<" "<<l<<" "<<r<<"\n";
    if(l==r){t[p].mx=t[p].lmx=t[p].rmx=t[p].sum=a[l];return;}
    int mid=(l+r)>>1;build(p*2,l,mid),build(p*2+1,mid+1,r);pushup(t[p],t[p*2],t[p*2+1]);
  }
  void ch(int p,int l,int r,int pt,int v){
    if(l==r){t[p].mx=t[p].lmx=t[p].rmx=t[p].sum=v;return;}int mid=(l+r)>>1;
    if(pt<=mid)ch(p*2,l,mid,pt,v);else ch(p*2+1,mid+1,r,pt,v);pushup(t[p],t[p*2],t[p*2+1]);
  }
  st ask(int p,int l,int r,int ll,int rr){
    if(ll<=l&&r<=rr)return t[p];int mid=(l+r)>>1;st res;
    if(rr<=mid)return ask(p*2,l,mid,ll,rr);
    if(ll>mid)return ask(p*2+1,mid+1,r,ll,rr);
    pushup(res,ask(p*2,l,mid,ll,rr),ask(p*2+1,mid+1,r,ll,rr));
    return res;
  }
}t1;

struct sgt2{
  struct st{
    ll sum[2],tg[2],mx;
  }t[N<<2];
  void pushup(st &p,st p1,st p2){
    p.sum[0]=max(p1.sum[0],p2.sum[0]);
    p.sum[1]=max(p2.sum[1],p2.sum[1]);
    p.mx=max({p1.mx,p2.mx,p1.sum[0]+p2.sum[1]});
  }
  void pushdown(int p){
    if(t[p].tg[0]!=0){
      t[p*2].sum[0]+=t[p].tg[0];t[p*2+1].sum[0]+=t[p].tg[0];
      t[p*2].tg[0]+=t[p].tg[0];t[p*2+1].tg[0]+=t[p].tg[0];
      t[p*2].mx+=t[p].tg[0],t[p*2+1].mx+=t[p].tg[0];t[p].tg[0]=0;
    }
    if(t[p].tg[1]!=0){
      t[p*2].sum[1]+=t[p].tg[1];t[p*2+1].sum[1]+=t[p].tg[1];
      t[p*2].tg[1]+=t[p].tg[1];t[p*2+1].tg[1]+=t[p].tg[1];
      t[p*2].mx+=t[p].tg[1],t[p*2+1].mx+=t[p].tg[1];t[p].tg[1]=0;
    }
  }
  void build(int p,int l,int r){//cout<<p<<" "<<l<<" "<<r<<"\n";
    if(l==r){
      t[p].sum[0]=pr[l],t[p].sum[1]=nx[l];
      t[p].tg[0]=t[p].tg[1]=0;t[p].mx=-8e18;return;
    }int mid=(l+r)>>1;build(p*2,l,mid),build(p*2+1,mid+1,r);
    pushup(t[p],t[p*2],t[p*2+1]);
  }
  void add(int p,int l,int r,int ll,int rr,int v,int w){
    if(ll<=l&&r<=rr){t[p].mx+=v,t[p].sum[w]+=v,t[p].tg[w]+=v;return;}int mid=(l+r)>>1;pushdown(p);
    if(ll<=mid)add(p*2,l,mid,ll,rr,v,w);if(rr>mid)add(p*2+1,mid+1,r,ll,rr,v,w);pushup(t[p],t[p*2],t[p*2+1]);
  }
  st ask(int p,int l,int r,int ll,int rr){if(c==1)assert(ll==rr);
    if(ll<=l&&r<=rr)return t[p];
    int mid=(l+r)>>1;pushdown(p);st res;
    if(rr<=mid)return ask(p*2,l,mid,ll,rr);
    if(ll>mid)return ask(p*2+1,mid+1,r,ll,rr);
    pushup(res,ask(p*2,l,mid,ll,rr),ask(p*2+1,mid+1,r,ll,rr));
    return res;
  }
}t2;

struct sgt3{
  ll mx[N<<2];
  void pushup(int p){mx[p]=max(mx[p*2],mx[p*2+1]);}
  void ch(int p,int l,int r,int pt,ll v){
    if(l==r){mx[p]=v;return;}int mid=(l+r)>>1;
    if(pt<mid)ch(p*2,l,mid,pt,v);
    else ch(p*2+1,mid+1,r,pt,v);pushup(p);
  }
  ll ask(int p,int l,int r,int ll,int rr){
    if(ll<=l&&r<=rr)return mx[p];int mid=(l+r)>>1;
    if(rr<=mid)return ask(p*2,l,mid,ll,rr);
    if(ll>mid)return ask(p*2+1,mid+1,r,ll,rr);
    return max(ask(p*2,l,mid,ll,rr),ask(p*2+1,mid+1,r,ll,rr));
  }
}t3,t4;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); 
  cin>>n>>q>>c;
  for(int i=1;i<=n;i++)cin>>a[i];
  while(n%c)n++;t1.build(1,1,n);//cout<<n<<"\n";
  for(int i=1;i<=n;i++)id[i]=(i-1)/c+1;
  for(int i=c+1;i<=n;i++){
    if(id[i]!=id[i-1])pr[i-c]=0;
    else pr[i-c]=pr[i-c-1];pr[i-c]+=a[i];//cout<<pr[i-c]<<"\n";
  }
  for(int i=n-c;i>=1;i--){
    if(id[i]!=id[i+1])nx[i]=0;
    else nx[i]=nx[i+1];nx[i]+=a[i];//cout<<nx[i]<<"\n";
  }
  t2.build(1,1,n-c);
  for(int i=1;i<=n;i+=c){
    t3.ch(1,1,n/c,(i-1)/c+1,t1.ask(1,1,n,i,i+c-1).mx);
    if(i<=n-1)t4.ch(1,1,n/c-1,(i-1)/c+1,t2.ask(1,1,n,i,i+c-1).mx);
  }
  int op,x,y;ll ans;
  for(int i=1;i<=q;i++){
    cin>>op>>x>>y;
    if(op==1){
      if(id[x]>1)t2.add(1,1,n-c,x-c,id[x]*c-c,y-a[x],0),
        t4.ch(1,1,n/c-1,id[x]-1,t2.ask(1,1,n-c,id[x]*c-c-c+1,id[x]*c-c).mx);//,cout<<t2.ask(1,1,n-c,id[x]*c-c-c+1,id[x]*c-c).mx<<"\n";
      if(id[x]<n/c)t2.add(1,1,n-c,id[x]*c-c+1,x,y-a[x],1),
        t4.ch(1,1,n/c-1,id[x],t2.ask(1,1,n-c,id[x]*c-c+1,id[x]*c).mx);
      t1.ch(1,1,n,x,y);a[x]=y;
      t3.ch(1,1,n/c,id[x],t1.ask(1,1,n,id[x]*c-c+1,id[x]*c).mx);
    }
    else{ans=0;
      if(y-x+1<=c)ans=max(ans,t1.ask(1,1,n,x,y).mx);
      else if(id[x]==id[y]-1){
        ans=max(ans,t2.ask(1,1,n-c,x,y-c).mx);//if(c==1)assert(ans==0);
        ans=max(ans,t1.ask(1,1,n,x,x+c-1).mx);
        ans=max(ans,t1.ask(1,1,n,y-c+1,y).mx);
      }
      else{
        if(id[y]-id[x]>2){
          ans=max(ans,t4.ask(1,1,n/c-1,id[x]+1,id[y]-2));
          if(c==1)assert(ans==0);
        }
        ans=max(ans,t3.ask(1,1,n/c,id[x]+1,id[y]-1));
        ans=max(ans,t2.ask(1,1,n-c,x,id[x]*c).mx);
        // if(c==1)assert(t2.ask(1,1,n-c,x,id[x]*c).mx==0);
        ans=max(ans,t1.ask(1,1,n,x,x+c-1).mx);
        ans=max(ans,t2.ask(1,1,n-c,id[y]*c-c+1,y).mx);
        // if(c==1)assert(t2.ask(1,1,n-c,id[y]*c-c+1,y).mx==0);
        ans=max(ans,t1.ask(1,1,n,y-c+1,y).mx);
      }
      cout<<ans<<"\n";
    }
  }return 0;
}