#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 4e5 + 10;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int n, m, c, A[N], B;

#define lc (u << 1)
#define rc (u << 1 | 1)
#define mid ((l + r) >> 1)
struct Max_Seg {
    ll C[N << 2];
    void Modify(int u, int l, int r, int p, ll x) {
        if(l == r) return C[u] = x, void();
        if(p <= mid) Modify(lc, l, mid, p, x);
        else Modify(rc, mid + 1, r, p, x);
        C[u] = max(C[lc], C[rc]);
    }
    ll Ask(int u, int l, int r, int L, int R) {
        if(l >= L && r <= R) return C[u];
        if(mid >= R) return Ask(lc, l, mid, L, R);
        if(mid < L) return Ask(rc, mid + 1, r, L, R);
        return max(Ask(lc, l, mid, L, R), Ask(rc, mid + 1, r, L, R));
    }
} Block, Other;
namespace SegmentTree {
    struct node {
        ll l, r, s, v;
        node(ll _v = 0) {l = r = v = max(_v, 0ll), s = _v; }
        node(ll _l, ll _r, ll _s, ll _v): l(_l), r(_r), s(_s), v(_v) {}
    };
    node operator + (const node &lhs, const node &rhs) {
        return node(max(lhs.l, lhs.s + rhs.l), max(rhs.r, rhs.s + lhs.r), lhs.s + rhs.s,
                max(lhs.r + rhs.l, max(lhs.v, rhs.v)));
    }
    node T[N << 2];
    void Build(int u, int l, int r) {
        if(l != r) 
            Build(lc, l, mid), Build(rc, mid + 1, r), T[u] = T[lc] + T[rc];
        else T[u] = node(A[l]);
    }
    void Modify(int u, int l, int r, int p, ll x) {
        if(l == r) return T[u] = node(x), void();
        if(p <= mid) Modify(lc, l, mid, p, x);
        else Modify(rc, mid + 1, r, p, x);
        T[u] = T[lc] + T[rc];
    }
    node Ask(int u, int l, int r, int L, int R) {
        if(l >= L && r <= R) return T[u];
        if(mid >= R) return Ask(lc, l, mid, L, R);
        if(mid < L) return Ask(rc, mid + 1, r, L, R);
        return Ask(lc, l, mid, L, R) + Ask(rc, mid + 1, r, L, R);
    }
}
struct Little_SegTree {
    struct node {
        ll ans, pre, suf;
        node(ll _ans = -INF, ll _pre = 0, ll _suf = 0): ans(_ans), pre(_pre), suf(_suf) {}
        node operator + (const node &rhs) {
            return node(max(this->pre + rhs.suf, max(this->ans, rhs.ans)), max(this->pre, rhs.pre), max(this->suf, rhs.suf));
        }
    };
    node *T; ll *tag_pre, *tag_suf;
    inline void init(int n) {
        T = (node*)calloc(n << 2, sizeof(node));
        tag_pre = (ll*)calloc(n << 2, sizeof(ll));
        tag_suf = (ll*)calloc(n << 2, sizeof(ll));
    }
    void Build(int u, int l, int r, ll pre[], ll suf[]) {
        tag_pre[u] = tag_suf[u] = 0;
        if(l != r) {
            Build(lc, l, mid, pre, suf), Build(rc, mid + 1, r, pre, suf);
            T[u] = T[lc] + T[rc];
        } else T[u] = node(pre[l] + suf[l], pre[l], suf[l]);
    }
    inline void Tag(int u, ll a, ll b) {
        tag_pre[u] += a, tag_suf[u] += b;
        T[u].pre += a, T[u].suf += b, T[u].ans += a + b;
    }
    inline void pushdown(int u) {
        if(!tag_pre[u] && !tag_suf[u]) return;
        Tag(lc, tag_pre[u], tag_suf[u]), Tag(rc, tag_pre[u], tag_suf[u]);
        tag_pre[u] = tag_suf[u] = 0;
    }
    void Add(int u, int l, int r, int L, int R, ll a, ll b) {
        if(l >= L && r <= R) return Tag(u, a, b);
        pushdown(u);
        if(mid >= L) Add(lc, l, mid, L, R, a, b);
        if(mid < R) Add(rc, mid + 1, r, L, R, a, b);
        T[u] = T[lc] + T[rc];
    }
    node Ask(int u, int l, int r, int L, int R) {
        if(l >= L && r <= R) return T[u];
        pushdown(u);
        if(mid >= R) return Ask(lc, l, mid, L, R);
        if(mid < L) return Ask(rc, mid + 1, r, L, R);
        return Ask(lc, l, mid, L, R) + Ask(rc, mid + 1, r, L, R);
    }
} Tree[N];
#undef lc
#undef rc
#undef mid

int L[N], R[N], ID[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m >> c;
    for(int i = 1; i <= n; i ++) cin >> A[i];
    n = (n + c - 1) / c * c, B = n / c;
    SegmentTree::Build(1, 1, n);
    
    for(int i = 1; i <= B; i ++) {
        static long long pre[N], suf[N];
        L[i] = (i - 1) * c + 1, R[i] = i * c;
        for(int j = L[i]; j <= R[i]; j ++) ID[j] = i;
        Block.Modify(1, 1, B, i, SegmentTree::Ask(1, 1, n, L[i], R[i]).v);
        if(i > 1) {
            pre[0] = suf[c] = 0;
            for(int j = 1; j <= c; j ++) pre[j] = pre[j - 1] + A[L[i] - j];
            for(int j = c - 1; j >= 0; j --) suf[j] = suf[j + 1] + A[L[i] + c - j - 1];
            Tree[i].init(c + 1); Tree[i].Build(1, 0, c, pre, suf);
            Other.Modify(1, 1, B, i, Tree[i].T[1].ans);
        }
    }

    while(m --) {
        int op, x, y; cin >> op >> x >> y;
        if(op == 1) {
            SegmentTree::Modify(1, 1, n, x, y);
            Block.Modify(1, 1, B, ID[x], SegmentTree::Ask(1, 1, n, L[ID[x]], R[ID[x]]).v);
            int pos = x - L[ID[x]];
            if(ID[x] > 1) {
                Tree[ID[x]].Add(1, 0, c, 0, c - pos, 0, y - A[x]);
                Other.Modify(1, 1, B, ID[x], Tree[ID[x]].T[1].ans);
            }
            if(ID[x] < B) {
                Tree[ID[x] + 1].Add(1, 0, c, R[ID[x]] - x + 1, c, y - A[x], 0);
                Other.Modify(1, 1, B, ID[x] + 1, Tree[ID[x] + 1].T[1].ans);
            }
            A[x] = y;
        } else {
            if(y - x + 1 > c) {
                ll ans = max(SegmentTree::Ask(1, 1, n, x, x + c - 1).v, SegmentTree::Ask(1, 1, n, y - c + 1, y).v);
                if(ID[x] + 1 < ID[y]) {
                    ans = max(ans, Block.Ask(1, 1, B, ID[x] + 1, ID[y] - 1));
                    if(ID[x] + 1 < ID[y] - 1) ans = max(ans, Other.Ask(1, 1, B, ID[x] + 2, ID[y] - 1));
                    ans = max(ans, Tree[ID[x] + 1].Ask(1, 0, c, 0, R[ID[x]] - x + 1).ans);
                    ans = max(ans, Tree[ID[y]].Ask(1, 0, c, c - (y - L[ID[y]] + 1), c).ans);
                } else 
                    ans = max(ans, Tree[ID[y]].Ask(1, 0, c, R[ID[y]] - y + 1, R[ID[x]] - x + 1).ans);
                cout << ans << '\n';
            } else cout << SegmentTree::Ask(1, 1, n, x, y).v << '\n';
        }
    }

    return 0;
}