#include <bits/stdc++.h>
#define N 200005
#define INF 1000000000000000000
#define ls(u) tr[u].ls
#define rs(u) tr[u].rs
using namespace std;
typedef long long ll;

int n, m, C, rec[N*2];
int bid[N], st[N];
ll _f[N*2], _g[N*2];

struct SegT1
{
    struct Seg { int ls, rs; ll f, g, sum, tgf, tgg; ll seq, lseq, rseq, aseq; } tr[N*2];
    int rt, tot;
    struct RET { ll f, g, sum; };
    struct RET2 { ll seq, lseq, rseq, aseq; };

    void pushdown (int u)
    {
        ll valf=tr[u].tgf, valg=tr[u].tgg;
        tr[ls(u)].f+=valf; tr[ls(u)].tgf+=valf; tr[ls(u)].sum+=valf;
        tr[rs(u)].f+=valf; tr[rs(u)].tgf+=valf; tr[rs(u)].sum+=valf;
        tr[ls(u)].g+=valg; tr[ls(u)].tgg+=valg; tr[ls(u)].sum+=valg;
        tr[rs(u)].g+=valg; tr[rs(u)].tgg+=valg; tr[rs(u)].sum+=valg;
        tr[u].tgf=0; tr[u].tgg=0;
    }
    void merge (int u)
    {
        tr[u].f=max(tr[ls(u)].f, tr[rs(u)].f);
        tr[u].g=max(tr[ls(u)].g, tr[rs(u)].g);
        tr[u].sum=max(tr[ls(u)].f+tr[rs(u)].g, max(tr[ls(u)].sum, tr[rs(u)].sum));
    }

    void build (int &u, int l, int r)
    {
        tr[u]=(Seg){ ls(u), rs(u), -INF, -INF, -INF, 0, 0, -INF, -INF, -INF, 0 };
        if (!u) { u=++tot; }
        if (l==r) {
            tr[u].f=_f[l+C]; tr[u].g=_g[l]; tr[u].sum=-INF;
            tr[u].seq=rec[l];
            tr[u].lseq=rec[l];
            tr[u].rseq=rec[l];
            tr[u].aseq=rec[l];
            return;
        }
        int md=(l+r)>>1;
        build(ls(u), l, md);
        build(rs(u), md+1, r);
        merge(u);

        tr[u].seq=max(tr[ls(u)].rseq+tr[rs(u)].lseq, max(tr[ls(u)].seq, tr[rs(u)].seq));
        tr[u].lseq=max(tr[ls(u)].lseq, tr[ls(u)].aseq+tr[rs(u)].lseq);
        tr[u].rseq=max(tr[rs(u)].rseq, tr[rs(u)].aseq+tr[ls(u)].rseq);
        tr[u].aseq=tr[ls(u)].aseq+tr[rs(u)].aseq;
    }

    void add_g (int u, int l, int r, int ql, int qr, ll num)
    {
        if (ql>r || qr<l) { return; }
        if (ql<=l && r<=qr) { tr[u].g+=num; tr[u].tgg+=num; tr[u].sum+=num; return; }
        pushdown(u);
        int md=(l+r)>>1;
        add_g(ls(u), l, md, ql, qr, num);
        add_g(rs(u), md+1, r, ql, qr, num);
        merge(u);
    }
    void add_f (int u, int l, int r, int ql, int qr, ll num)
    {
        if (ql>r || qr<l) { return; }
        if (ql<=l && r<=qr) { tr[u].f+=num; tr[u].tgf+=num; tr[u].sum+=num; return; }
        pushdown(u);
        int md=(l+r)>>1;
        add_f(ls(u), l, md, ql, qr, num);
        add_f(rs(u), md+1, r, ql, qr, num);
        merge(u);
    }
    RET qry (int u, int l, int r, int ql, int qr)
    {
        if (ql>r || qr<l) { return (RET){ -INF, -INF, -INF }; }
        if (ql<=l && r<=qr) { return (RET){ tr[u].f, tr[u].g, tr[u].sum }; }
        pushdown(u);
        int md=(l+r)>>1;
        RET resl=qry(ls(u), l, md, ql, qr);
        RET resr=qry(rs(u), md+1, r, ql, qr);
        return (RET){ max(resl.f, resr.f), max(resl.g, resr.g), max(resl.f+resr.g, max(resl.sum, resr.sum)) };
    }

    void upd_seq (int u, int l, int r, int id, ll num)
    {
        if (l==r) { tr[u].seq=tr[u].lseq=tr[u].rseq=tr[u].aseq=num; return; }
        int md=(l+r)>>1;
        if (id<=md) { upd_seq(ls(u), l, md, id, num); }
        else { upd_seq(rs(u), md+1, r, id, num); }

        tr[u].seq=max(tr[ls(u)].rseq+tr[rs(u)].lseq, max(tr[ls(u)].seq, tr[rs(u)].seq));
        tr[u].lseq=max(tr[ls(u)].lseq, tr[ls(u)].aseq+tr[rs(u)].lseq);
        tr[u].rseq=max(tr[rs(u)].rseq, tr[rs(u)].aseq+tr[ls(u)].rseq);
        tr[u].aseq=tr[ls(u)].aseq+tr[rs(u)].aseq;
    }
    RET2 qry_seq (int u, int l, int r, int ql, int qr)
    {
        if (ql>r || qr<l) { return (RET2){ -INF, -INF, -INF, 0 }; }
        if (ql<=l && r<=qr) { return (RET2){ tr[u].seq, tr[u].lseq, tr[u].rseq, tr[u].aseq }; }
        int md=(l+r)>>1;
        RET2 resl=qry_seq(ls(u), l, md, ql, qr);
        RET2 resr=qry_seq(rs(u), md+1, r, ql, qr);
        RET2 res;
        res.seq=max(resl.rseq+resr.lseq, max(resl.seq, resr.seq));
        res.lseq=max(resl.lseq, resl.aseq+resr.lseq);
        res.rseq=max(resr.rseq, resr.aseq+resl.rseq);
        res.aseq=resl.aseq+resr.aseq;
        return res;
    }
} ST1;

struct SegT2
{
    struct Seg { int ls, rs; ll seq, sum; } tr[N*2];
    int rt, tot;

    void build (int &u, int l, int r)
    {
        if (!u) { u=++tot; }
        if (l==r) {
            tr[u].seq=ST1.qry_seq(ST1.rt, 1, n, st[bid[l]], st[bid[l]+1]-1).seq;
            tr[u].sum=ST1.qry(ST1.rt, 1, n, st[bid[l]], st[bid[l]+1]-1).sum;
            return;
        }
        int md=(l+r)>>1;
        build(ls(u), l, md); build(rs(u), md+1, r);
        tr[u].seq=max(tr[ls(u)].seq, tr[rs(u)].seq);
        tr[u].sum=max(tr[ls(u)].sum, tr[rs(u)].sum);
    }
    void upd (int u, int l, int r, int id, ll sum, ll seq)
    {
        if (l==r) { tr[u].sum=sum; tr[u].seq=seq; return; }
        int md=(l+r)>>1;
        if (id<=md) { upd(ls(u), l, md, id, sum, seq); }
        else { upd(rs(u), md+1, r, id, sum, seq); }
        tr[u].seq=max(tr[ls(u)].seq, tr[rs(u)].seq);
        tr[u].sum=max(tr[ls(u)].sum, tr[rs(u)].sum);
    }
    ll qry_seq (int u, int l, int r, int ql, int qr)
    {
        if (ql>r || qr<l) { return -INF; }
        if (ql<=l && r<=qr) { return tr[u].seq; }
        int md=(l+r)>>1;
        return max(qry_seq(ls(u), l, md, ql, qr), qry_seq(rs(u), md+1, r, ql, qr));
    }
    ll qry_sum (int u, int l, int r, int ql, int qr)
    {
        if (ql>r || qr<l) { return -INF; }
        if (ql<=l && r<=qr) { return tr[u].sum; }
        int md=(l+r)>>1;
        return max(qry_sum(ls(u), l, md, ql, qr), qry_sum(rs(u), md+1, r, ql, qr));
    }
    void uupd (int pos, ll sum, ll seq)
    {
        upd(rt, 1, bid[n], pos, sum, seq);
    }

} ST2;


void uupd (int pos, int num)
{
    ll ad=num-rec[pos];
    ST1.add_g(ST1.rt, 1, n, st[bid[pos]], pos, ad);
    if (bid[pos]>1) { ST1.add_f(ST1.rt, 1, n, pos-C, st[bid[pos]]-1, ad); }
    ST1.upd_seq(ST1.rt, 1, n, pos, num);
    rec[pos]=num;

    int x=bid[pos];
    ST2.uupd(x, ST1.qry(ST1.rt, 1, n, st[x], st[x+1]-1).sum, ST1.qry_seq(ST1.rt, 1, n, st[x], st[x+1]-1).seq);
    x=bid[pos]-1;
    if (x>=1) { ST2.uupd(x, ST1.qry(ST1.rt, 1, n, st[x], st[x+1]-1).sum, ST1.qry_seq(ST1.rt, 1, n, st[x], st[x+1]-1).seq); }
}

int main ()
{
    // freopen("0test.in", "r", stdin);
    // freopen("0test.out", "w", stdout);

    scanf("%d %d %d", &n, &m, &C);
    for (int i=1; i<=n; i++) { scanf("%d", &rec[i]); }

    for (int i=1; i<=n; i++) {
        bid[i]=((i-1)/C)+1;
        if (!st[bid[i]]) { st[bid[i]]=i; }
    } st[bid[n]+1]=n+1;

    for (int i=1; i<=n; i++) {
        _f[i]=(i!=st[bid[i]])*_f[i-1]+rec[i];
    }
    for (int i=n; i>=1; i--) {
        _g[i]=(i!=st[bid[i]+1]-1)*_g[i+1]+rec[i];
    }

    ST1.build(ST1.rt, 1, n);
    ST2.build(ST2.rt, 1, bid[n]);

    // for (int i=1; i<=n; i++) {
    //     cout<<ST1.qry(ST1.rt, 1, n, i, i).sum<<" ";
    // }
    // cout<<endl;

    // for (int i=1; i<=bid[n]; i++) {
    //     // cout<<ST1.qry(ST1.rt, 1, n, st[i], st[i+1]-1).sum<<" ";
    //     // cout<<ST1.qry_seq(ST1.rt, 1, n, st[i], st[i+1]-1).seq<<endl;
    //     cout<<ST2.qry_seq(ST2.rt, 1, n, i, i)<<" ";
    // }
    // cout<<endl;

    for (int t=1; t<=m; t++) {
        int op; scanf("%d", &op);
        if (op==1) {
            int x, y; scanf("%d %d", &x, &y); uupd(x, y);
            cout<<"?\n";
        }
        else {
            int l, r; scanf("%d %d", &l, &r);

            ll ans=0;
            if (r-l+1<=C) {
                ans=max(ans, ST1.qry_seq(ST1.rt, 1, n, l, r).seq);
            }
            else if (bid[l]==bid[r]-1) {
                ans=max(ans, ST1.qry_seq(ST1.rt, 1, n, l, l+C-1).seq);
                ans=max(ans, ST1.qry_seq(ST1.rt, 1, n, r-C+1, r).seq);
                ans=max(ans, ST1.qry(ST1.rt, 1, n, l, r-C).sum);
            }
            else {
                ans=max(ans, ST2.qry_seq(ST2.rt, 1, bid[n], bid[l]+1, bid[r]-1));
                if (bid[l]+1<=bid[r]-1) {
                    ans=max(ans, ST2.qry_sum(ST2.rt, 1, bid[n], bid[l]+1, bid[r]-2));
                }
                ans=max(ans, ST1.qry_seq(ST1.rt, 1, n, l, l+C-1).seq);
                ans=max(ans, ST1.qry_seq(ST1.rt, 1, n, r-C+1, r).seq);
                ans=max(ans, ST1.qry(ST1.rt, 1, n, st[bid[r]-1], r-C).sum);
                ans=max(ans, ST1.qry(ST1.rt, 1, n, l, st[bid[l]+1]-1).sum);
            }

            printf("%lld\n", ans);
        }
    }

    return 0;
}