#include <bits/stdc++.h>
using i64 = long long;
const int N = 4e5;
const i64 Inf = 1e18;
namespace Segment_Tree1 {

struct Tag {
    i64 s[2];
    void operator+=(const Tag &p) { for (auto i : {0, 1}) s[i] += p.s[i]; }
};
struct Data {
    i64 mx[3];
    Data operator+(const Data &p) const{
        Data res;
        for (auto i : {0, 1, 2}) res.mx[i] = std::max(mx[i], p.mx[i]);
        res.mx[2] = std::max(res.mx[2], mx[0] + p.mx[1]);
        return res;
    }
    void operator+=(const Tag &p) {
        mx[0] += p.s[0], mx[1] += p.s[1], mx[2] = mx[2] + p.s[0] + p.s[1];
    }
};
const int N = ::N * 4;
struct Node { int l, r, ls, rs; Data s; Tag t; }ar[N + 5];
int tot;
#define mid ((ar[k].l + ar[k].r) >> 1)
#define ls(k) ar[k].ls
#define rs(k) ar[k].rs
void pushup(int k) { ar[k].s = ar[ls(k)].s + ar[rs(k)].s; }
void build(int l, int r, int &k, int *a, int *b) {
    k = ++tot, ar[k].l = l, ar[k].r = r;
    if (l == r) ar[k].s = {a[l], b[l], -Inf};
    else build(l, mid, ls(k), a, b), build(mid + 1, r, rs(k), a, b), pushup(k);
}
void modify(int k, Tag v) { ar[k].s += v, ar[k].t += v; }
void pushdown(int k) { modify(ls(k), ar[k].t), modify(rs(k), ar[k].t), ar[k].t = {0, 0}; }
void update(int l, int r, Tag v, int k) {
    if (l > ar[k].r or r < ar[k].l) return ;
    if (l <= ar[k].l and r >= ar[k].r) return modify(k, v);
    pushdown(k), update(l, r, v, ls(k)), update(l, r, v, rs(k)), pushup(k);
}
Data query(int l, int r, int k) {
    if (l > ar[k].r or r < ar[k].l) return {-Inf, -Inf, -Inf};
    if (l <= ar[k].l and r >= ar[k].r) return ar[k].s;
    pushdown(k);
    return query(l, r, ls(k)) + query(l, r, rs(k));
}
#undef mid
#undef ls
#undef rs

}
namespace Segment_Tree2 {

const int N = ::N * 4;
struct Node { int l, r, ls, rs; i64 s; }ar[N + 5];
int tot;
#define mid ((ar[k].l + ar[k].r) >> 1)
#define ls(k) ar[k].ls
#define rs(k) ar[k].rs
void pushup(int k) { ar[k].s = std::max(ar[ls(k)].s, ar[rs(k)].s); }
void build(int l, int r, int &k) {
    k = ++tot, ar[k].l = l, ar[k].r = r;
    if (l < r) build(l, mid, ls(k)), build(mid + 1, r, rs(k)), pushup(k);
}
void update(int x, i64 v, int k) {
    if (x > ar[k].r or x < ar[k].l) return ;
    if (ar[k].l == ar[k].r) { ar[k].s = v; return ; }
    update(x, v, ls(k)), update(x, v, rs(k)), pushup(k);
}
i64 query(int l, int r, int k) {
    if (l > ar[k].r or r < ar[k].l) return -Inf;
    if (l <= ar[k].l and r >= ar[k].r) return ar[k].s;
    return std::max(query(l, r, ls(k)), query(l, r, rs(k)));
}
#undef mid
#undef ls
#undef rs

}
int n, q, c, a[N + 5], pos[N + 5], lb[N + 5], rb[N + 5];
int sump[N + 5], sumn[N + 5], rti[N + 5], rtc[N + 5], pre[N + 5], suf[N + 5];
int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    std::cin >> n >> q >> c;
    for (int i = 1; i <= n; ++i) std::cin >> a[i], pos[i] = (i - 1) / c + 1;
    for (int i = n + 1; i <= pos[n] * c; ++i) pos[i] = pos[n];
    n = pos[n] * c;
    for (int i = 1; i <= pos[n]; ++i) lb[i] = rb[i - 1] + 1, rb[i] = i * c;
    Segment_Tree2::build(1, pos[n], rti[0]);
    for (int i = 1; i <= pos[n]; ++i) {
        for (int j = lb[i]; j <= rb[i]; ++j) sump[j] = sump[j - 1] + a[j], sumn[j] = sumn[j - 1] - a[j];
        Segment_Tree1::build(lb[i] - 1, rb[i], rti[i], sumn, sump), sump[rb[i]] = sumn[rb[i]] = 0;
        Segment_Tree2::update(i, Segment_Tree1::query(lb[i] - 1, rb[i], rti[i]).mx[2], rti[0]);
    }
    for (int i = 1; i < pos[n]; ++i)
        for (int j = rb[i]; j >= lb[i]; --j) suf[j] = suf[j + 1] + a[j];
    for (int i = pos[n]; i > 1; --i)
        for (int j = lb[i]; j <= rb[i]; ++j) pre[j - c] = pre[j - 1 - c] + a[j];
    Segment_Tree2::build(1, pos[n] - 1, rtc[0]);
    for (int i = 1; i < pos[n]; ++i) {
        Segment_Tree1::build(lb[i], rb[i], rtc[i], pre, suf);
        Segment_Tree2::update(i, Segment_Tree1::query(lb[i], rb[i], rtc[i]).mx[2], rtc[0]);
    }
    for (int op, x, y; q--;) {
        std::cin >> op >> x >> y;
        if (op == 1) {
            y -= a[x];
            int p = pos[x];
            Segment_Tree1::update(x, rb[p], {-y, y}, rti[p]);
            Segment_Tree2::update(p, Segment_Tree1::query(lb[p] - 1, rb[p], rti[p]).mx[2], rti[0]);
            if (p < pos[n]) {
                Segment_Tree1::update(lb[p], x, {0, y}, rtc[p]);
                Segment_Tree2::update(p, Segment_Tree1::query(lb[p], rb[p], rtc[p]).mx[2], rtc[0]);
            }
            if (p > 1) {
                Segment_Tree1::update(x - c, rb[p] - c, {y, 0}, rtc[p - 1]);
                Segment_Tree2::update(p - 1, Segment_Tree1::query(lb[p - 1], rb[p - 1], rtc[p - 1]).mx[2], rtc[0]);
            }
            a[x] = y;
        }else {
            int p = pos[x], q = pos[y];
            i64 ans = 0;
            if (p == q) ans = std::max(ans, Segment_Tree1::query(x - 1, y, rti[p]).mx[2]);
            else {
                ans = std::max(ans, Segment_Tree1::query(x - 1, rb[p], rti[p]).mx[2]);
                ans = std::max(ans, Segment_Tree1::query(lb[q] - 1, y, rti[q]).mx[2]);
                ans = std::max(ans, Segment_Tree2::query(p + 1, q - 1, rti[0]));
                ans = std::max(ans, Segment_Tree2::query(p + 1, q - 2, rtc[0]));
                if (p == q - 1) {
                    ans = std::max(ans, Segment_Tree1::query(x, y - c, rtc[p]).mx[2]);
                    ans = std::max(ans, Segment_Tree1::query(x, rb[p], rtc[p]).mx[1]
                                    + Segment_Tree1::query(lb[p], y - c, rtc[p]).mx[0]);
                }else {
                    ans = std::max(ans, Segment_Tree1::query(x, rb[p], rtc[p]).mx[2]);
                    ans = std::max(ans, Segment_Tree1::query(x, rb[p], rtc[p]).mx[1]
                                    + Segment_Tree1::query(lb[p], x - 1, rtc[p]).mx[0]);
                    ans = std::max(ans, Segment_Tree1::query(lb[q] - c, y - c, rtc[q - 1]).mx[2]);
                    ans = std::max(ans, Segment_Tree1::query(lb[q] - c, y - c, rtc[q - 1]).mx[0]
                                    + Segment_Tree1::query(y + 1 - c, rb[q] - c, rtc[q - 1]).mx[1]);
                }
            }
            std::cout << ans << "\n";
        }
    }
    return 0;
}