#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

long long States[N * 20], *nowState = States;

inline long long* myMalloc(int sz, int flg = 0)
{
    long long *sta = nowState;
    nowState += sz;
    if (flg) {
        fill(sta, nowState, (long long)-1e18);
    }
    return sta;
}

char I[40000050], *J = I, O[8000050], *o = O;

inline int read()
{
    unsigned int x = 0;
    bool zf = 0;
    while ((*J < 48 || 57 < *J) && (*J) != '-') ++J;
    ((*J++ == '-') ? (zf = 1) : x = *(J - 1) ^ 48);
    while (47 < *J && *J < 58) x = (x << 1) + (x << 3) + (*J++ ^ 48);
    return (zf ? -(int)x : x);
}

inline void print(unsigned long long x)
{
    static unsigned long long S[16], T = 0, y;
    do y = x / 10, S[T++] = x - y * 10; while(x = y);
    while (T) *o++ = S[--T] ^ 48;
}

int n, m, C;
long long a[N];

namespace SEG1
{
    typedef long long LL;
    typedef tuple<LL, LL, LL, LL> dt;
    int sz;
    dt z[1 << 22];

    inline dt operator + (dt x, dt y)
    {
        auto [a, b, c, d] = x;
        auto [e, f, g, h] = y;
        return {a + e, max({b, f, d + g}), max(c, a + g), max(h, e + d)};
    }

    inline void build()
    {
        sz = 1;
        while (sz <= n + 1) {
            sz <<= 1;
        }
        for (int i = 1; i <= n; ++i) {
            z[i + sz] = {a[i], max(a[i], 0ll), max(a[i], 0ll), max(a[i], 0ll)};
        }
        for (int i = (n + sz) >> 1; i; --i) {
            z[i] = z[i << 1] + z[i << 1 | 1];
        }
        return;
    }

    inline void modify(int x)
    {
        z[x + sz] = {a[x], max(a[x], 0ll), max(a[x], 0ll), max(a[x], 0ll)};
        x += sz;
        while (x >>= 1) {
            z[x] = z[x << 1] + z[x << 1 | 1];
        }
        return;
    }

    inline long long query(int L, int R)
    {
        dt rL = {0, 0, 0, 0}, rR = {0, 0, 0, 0};
        for (L += sz - 1, R += sz + 1; L ^ R ^ 1; L >>= 1, R >>= 1) {
            (!(L & 1)) && (rL = rL + z[L ^ 1], 0);
            (R & 1) && (rR = z[R ^ 1] + rR, 0);
        }
        auto [A, B, C, D] = rL + rR;
        return B;
    }

    inline long long cb(dt z)
    {
        auto &[A, B, C, D] = z;
        return A;
    }

    inline long long querySum(int L, int R)
    {
        if (L > R) {
            return 0ll;
        }
        long long S = 0;
        for (L += sz - 1, R += sz + 1; L ^ R ^ 1; L >>= 1, R >>= 1) {
            (!(L & 1)) && (S += cb(z[L ^ 1]), 0);
            (R & 1) && (S += cb(z[R ^ 1]), 0);
        }
        return S;
    }
}

int bl;
long long glo1[N], glo2[N];

namespace SEG2
{
    int n, sz;
    long long mx[1 << 22];

    inline void build()
    {
        n = bl - 2, sz = 1;
        while (sz <= n + 1) {
            sz <<= 1;
        }
        for (int i = 1; i <= n; ++i) {
            mx[i + sz] = max(glo1[i], glo2[i]);
        }
        for (int i = (n + sz) >> 1; i; --i) {
            mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
        }
        return;
    }

    inline void modify(int x)
    {
        mx[x + sz] = max(glo1[x], glo2[x]);
        x += sz;
        while (x >>= 1) {
            mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
        }
        return;
    }

    inline long long query(int L, int R)
    {
        long long res = 0;
        for (L += sz - 1, R += sz + 1; L ^ R ^ 1; L >>= 1, R >>= 1) {
            (!(L & 1)) && (res = max(res, mx[L ^ 1]));
            ((R & 1)) && (res = max(res, mx[R ^ 1]));
        }
        return res;
    }
}

long long Sa[N], Sb[N];

inline tuple<long long, long long, long long, long long, long long> operator + (tuple<long long, long long, long long, long long, long long> x, tuple<long long, long long, long long, long long, long long> y);

struct DS
{
    int len, sz;

    typedef long long LL;
    
    LL *SuA, *SuB, *MxA, *MxB, *S;

    friend inline tuple<LL, LL, LL, LL, LL> operator + (tuple<LL, LL, LL, LL, LL> x, tuple<LL, LL, LL, LL, LL> y)
    {
        auto &[A, B, C, D, E] = x;
        auto &[F, G, H, I, J] = y;
        return {A + F, B + G, max(H, C + F), max(D, I + B), max({E + F, J + B, H + D})};
    }

    inline void Build()
    {
        int t = 2 * len, z = 1;
        while (z <= t + 1) {
            z <<= 1;
        }
        sz = z;
        SuA = myMalloc(len + sz + 1);
        SuB = myMalloc(len + sz + 1);
        MxA = myMalloc(len + sz + 1, 1);
        MxB = myMalloc(len + sz + 1, 1);
        S = myMalloc(len + z + 1, 1);
        for (int i = 1; i <= len; ++i) {
            SuA[i + sz] = MxA[i + sz] = Sa[i];
            SuB[i + sz] = MxB[i + sz] = Sb[i];
            S[i + sz] = -1e18;
        }
        for (int k = (len + z) >> 1; k; --k) {
            SuA[k] = SuA[k << 1] + SuA[k << 1 | 1];
            SuB[k] = SuB[k << 1] + SuB[k << 1 | 1];
            MxA[k] = max(MxA[k << 1 | 1], SuA[k << 1 | 1] + MxA[k << 1]);
            MxB[k] = max(MxB[k << 1], SuB[k << 1] + MxB[k << 1 | 1]);
            S[k] = max({S[k << 1] + SuA[k << 1 | 1], S[k << 1 | 1] + SuB[k << 1], MxA[k << 1 | 1] + MxB[k << 1]});
        }
        return;
    }

    inline long long query(int L, int R)
    {
        tuple<LL, LL, LL, LL, LL> tA, tB;
        for (L += sz - 1, R += sz + 1; L ^ R ^ 1; L >>= 1, R >>= 1) {
            (!(L & 1)) && (tA = tA + tuple<LL, LL, LL, LL, LL>{SuA[L ^ 1], SuB[L ^ 1], MxA[L ^ 1], MxB[L ^ 1], S[L ^ 1]}, 0);
            ((R & 1)) && (tB = tuple<LL, LL, LL, LL, LL>{SuA[R ^ 1], SuB[R ^ 1], MxA[R ^ 1], MxB[R ^ 1], S[R ^ 1]} + tB, 0);
        }
        auto [A, B, C, D, E] = tA + tB;
        return E;
    }

    inline void modifyA(int k, int y)
    {
        k += sz;
        SuA[k] += y, MxA[k] += y;
        while (k >>= 1) {
            SuA[k] = SuA[k << 1] + SuA[k << 1 | 1];
            MxA[k] = max(MxA[k << 1 | 1], SuA[k << 1 | 1] + MxA[k << 1]);
            S[k] = max({S[k << 1] + SuA[k << 1 | 1], S[k << 1 | 1] + SuB[k << 1], MxA[k << 1 | 1] + MxB[k << 1]});
        }
        return;
    }

    inline void modifyB(int k, int y)
    {
        k += sz;
        SuB[k] += y, MxB[k] += y;
        while (k >>= 1) {
            SuB[k] = SuB[k << 1] + SuB[k << 1 | 1];
            MxB[k] = max(MxB[k << 1], SuB[k << 1] + MxB[k << 1 | 1]);
            S[k] = max({S[k << 1] + SuA[k << 1 | 1], S[k << 1 | 1] + SuB[k << 1], MxA[k << 1 | 1] + MxB[k << 1]});
        }
        return;
    }

    inline void modify(int type, int x, int y)
    {
        if (!type) {
            modifyA(x, y);
        } else {
            modifyB(x, y);
        }
        return;
    }
} SEG3[N];

inline long long calc(int wh, int L = 0, int R = 0, long long V = 0)
{
    if (!L) {
        return SEG3[wh].S[1];
    }
    if (SEG1::query(L, R + C) <= V) {
        return V;
    }
    L -= (wh - 1) * C, R -= (wh - 1) * C;
    return SEG3[wh].query(L, R) + SEG1::querySum(wh * C + 1, wh * C + L - 1) + SEG1::querySum((wh - 1) * C + R + 1, wh * C);
}

signed main()
{
    fread(I, 1, 40000038, stdin);
    n = read(), m = read(), C = read();
    bl = (n - 1) / C + 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }
    SEG1::build();
    for (int i = 2; i <= bl - 1; ++i) {
        long long s = 0, mx = 0;
        for (int j = (i - 1) * C + 1; j <= i * C && j <= n; ++j) {
            mx = max(mx, s = max(s, 0ll) + a[j]);
        }
        glo1[i] = mx;
    }
    for (int i = 1; i <= bl - 1; ++i) {
        SEG3[i].len = min((i + 1) * C, n) - i * C;
        for (int j = 1; j <= SEG3[i].len; ++j) {
            Sa[j] = 0;
        }
        for (int j = 1; j <= C && j + (i - 1) * C <= n; ++j) {
            Sa[min(j, SEG3[i].len)] += a[j + (i - 1) * C];
        }
        for (int j = 1; j <= SEG3[i].len; ++j) {
            Sb[j] = a[j + i * C];
        }
        SEG3[i].Build();
    }
    for (int i = 2; i <= bl - 2; ++i) {
        glo2[i] = calc(i);
    }
    SEG2::build();
    while (m--) {
        int opt = read(), L = read(), R = read();
        if (opt == 1) {
            if (a[L] == R) {
                continue;
            }
            int D = R - a[L];
            a[L] = R;
            SEG1::modify(L);
            int bel = (L - 1) / C + 1;
            long long flg = max(glo1[bel], glo2[bel]);
            if (bel >= 2 && bel <= bl - 1) {
                glo1[bel] = SEG1::query((bel - 1) * C + 1, bel * C);
            }
            if (bel >= 2) {
                SEG3[bel - 1].modify(1, L - (bel - 1) * C, D);
            }
            if (bel <= bl - 1) {
                SEG3[bel].modify(0, L - (bel - 1) * C, D);
            }
            if (bel >= 3) {
                long long tv = max(glo1[bel - 1], glo2[bel - 1]);
                glo2[bel - 1] = calc(bel - 1);
                if (max(glo1[bel - 1], glo2[bel - 1]) != tv && bel <= bl - 1) {
                    SEG2::modify(bel - 1);
                }
            }
            if (bel >= 2 && bel <= bl - 2) {
                glo2[bel] = calc(bel);
            }
            if (bel >= 2 && bel <= bl - 2 && flg != max(glo1[bel], glo2[bel])) {
                SEG2::modify(bel);
            }
        } else {
            if (R - L + 1 <= C) {
                print(SEG1::query(L, R));
                *o++ = '\n';
                continue;
            }
            int bel = (L - 1) / C + 1, ber = (R - 1) / C + 1;
            long long res = (bel + 2 >= ber ? 0ll : SEG2::query(bel + 1, ber - 2));
            if (bel + 1 != ber) {
                res = max(res, glo1[ber - 1]);
            }
            res = max({res, SEG1::query(L, L + C - 1), SEG1::query(R - C + 1, R)});
            if (ber == bel + 1) {
                res = max(res, calc(bel, L, R - C, res));
            } else {
                res = max({res, calc(bel, L, bel * C, res), calc(ber - 1, (ber - 2) * C + 1, R - C, res)});
            }
            print(res);
            *o++ = '\n';
        }
    }
    fwrite(O, 1, o - O, stdout);
    return 0;
}