#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int maxn = 200000;
struct SEG1 {
	struct item {
		i64 mx, pre, suf, sum;
		item(int v = 0) : sum(v) { mx = pre = suf = max(v, 0); }
		item operator+(const item& b) const {
			item c;
			c.sum = sum + b.sum;
			c.mx = max(max(mx, b.mx), suf + b.pre);
			c.pre = max(pre, sum + b.pre);
			c.suf = max(b.suf, b.sum + suf);
			return c;
		}
	} t[4 * maxn + 5];
	inline void pushup(int p) { t[p] = t[p << 1] + t[p << 1 | 1]; }
	void build(int p, int l, int r, int v[]) {
		if (l == r) return t[p] = item(v[l]), void();
		int mid = (l + r) / 2;
		build(p << 1, l, mid, v), build(p << 1 | 1, mid + 1, r, v);
		pushup(p);
	}
	void modify(int p, int l, int r, int x, int v) {
		if (l == r) return t[p] = item(v), void();
		int mid = (l + r) / 2;
		if (mid >= x) modify(p << 1, l, mid, x, v);
		else modify(p << 1 | 1, mid + 1, r, x, v);
		pushup(p);
	}
	item query(int p, int l, int r, int x, int y) {
		if (x <= l && r <= y) return t[p];
		int mid = (l + r) / 2; item rs;
		if (mid >= x) rs = rs + query(p << 1, l, mid, x, y);
		if (mid < y) rs = rs + query(p << 1 | 1, mid + 1, r, x, y);
		return rs;
	}
} t1;
struct SEG2 {
	struct item {
		i64 mx, pre, suf;
		item(i64 mx = 0, i64 pre = 0, i64 suf = 0) : mx(mx), pre(pre), suf(suf) {}
		item operator+(const item& b) const {
			item c;
			c.mx = max(max(mx, b.mx), pre + b.suf);
			c.pre = max(pre, b.pre), c.suf = max(suf, b.suf);
			return c; 
		}
	};
	item *t;
	i64 *tg1, *tg2;
	void init(int len) {
		t = (item*)calloc(4 * len, sizeof(item));
		tg1 = (i64*)calloc(4 * len, sizeof(i64)), tg2 = (i64*)calloc(4 * len, sizeof(i64));
	}
	inline void mark(int p, i64 v1, i64 v2) {
		t[p].pre += v1, tg1[p] += v1;
		t[p].suf += v2, tg2[p] += v2;
		t[p].mx += v1 + v2;
	}
	inline void pushdown(int p) {
		if (!tg1[p] && !tg2[p]) return;
		mark(p << 1, tg1[p], tg2[p]), mark(p << 1 | 1, tg1[p], tg2[p]);
		tg1[p] = tg2[p] = 0;
	}
	inline void pushup(int p) { t[p] = t[p << 1] + t[p << 1 | 1]; }
	void build(int p, int l, int r, i64 v1[], i64 v2[]) {
		if (l == r) return t[p] = item(-1E18, v2[l], v1[l]), void();
		int mid = (l + r) / 2;
		build(p << 1, l, mid, v1, v2), build(p << 1 | 1, mid + 1, r, v1, v2);
		pushup(p);
	}
	void modify(int p, int l, int r, int x, int y, int v1, int v2) {
		if (x <= l && r <= y) return mark(p, v1, v2);
		pushdown(p);
		int mid = (l + r) / 2;
		if (mid >= x) modify(p << 1, l, mid, x, y, v1, v2);
		if (mid < y) modify(p << 1 | 1, mid + 1, r, x, y, v1, v2);
		pushup(p);
	}
	item query(int p, int l, int r, int x, int y) {
		if (x <= l && r <= y) return t[p];
		pushdown(p);
		int mid = (l + r) / 2; item rs;
		if (mid >= x) rs = rs + query(p << 1, l, mid, x, y);
		if (mid < y) rs = rs + query(p << 1 | 1, mid + 1, r, x, y);
		return rs;
	}
} t2[maxn + 5];
struct SEG3 {
	i64 mx[4 * maxn + 5];
	inline void pushup(int p) { mx[p] = max(mx[p << 1], mx[p << 1 | 1]); }
	void modify(int p, int l, int r, int x, i64 v) {
		if (l == r) return mx[p] = v, void();
		int mid = (l + r) / 2;
		if (mid >= x) modify(p << 1, l, mid, x, v);
		else modify(p << 1 | 1, mid + 1, r, x, v);
		pushup(p);
	}
	i64 query(int p, int l, int r, int x, int y) {
		if (x <= l && r <= y) return mx[p];
		int mid = (l + r) / 2; i64 rs = 0;
		if (mid >= x) rs = max(rs, query(p << 1, l, mid, x, y));
		if (mid < y) rs = max(rs, query(p << 1 | 1, mid + 1, r, x, y));
		return rs;
	}
} t3, t4;
int lp[maxn + 5], rp[maxn + 5];
int a[2 * maxn + 5];
i64 pre[maxn + 5], suf[maxn + 5];
int main() {
	int n, m, c;
	scanf("%d%d%d", &n, &m, &c);
	int t = (n + c - 1) / c;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	t1.build(1, 1, n, a);
	for (int i = 1; i <= t; i++) {
		lp[i] = (i - 1) * c + 1, rp[i] = min(i * c, n);
		t3.modify(1, 1, t, i, t1.query(1, 1, c, lp[i], rp[i]).mx);
		if (i > 1) {
			for (int j = 1; j <= c; j++) pre[j] = pre[j - 1] + a[j + lp[i] - 1];
			for (int j = c; j >= 1; j--) suf[j] = suf[j + 1] + a[j + lp[i] - c - 1];
			t2[i].init(c), t2[i].build(1, 1, c, suf, pre);
			t4.modify(1, 1, t, i, t2[i].t[1].mx);
		}
	}
	for (int i = 1; i <= m; i++) {
		int op, x, y;
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) {
			t1.modify(1, 1, n, x, y);
			int b = (x - 1) / c + 1, id = x - (b - 1) * c;
			t3.modify(1, 1, t, b, t1.query(1, 1, c, lp[b], rp[b]).mx);
			if (b > 1) {
				t2[b].modify(1, 1, c, id, c, y - a[x], 0);
				t4.modify(1, 1, t, b, t2[b].t[1].mx);
			}
			if (b < t) {
				t2[b + 1].modify(1, 1, c, 1, id, 0, y - a[x]);
				t4.modify(1, 1, t, b + 1, t2[b + 1].t[1].mx);
			}
			a[x] = y;
		} else {
			int bx = (x - 1) / c + 1, by = (y - 1) / c + 1;
			int idx = x - (bx - 1) * c, idy = y - (by - 1) * c;
			i64 ans = 0;
			if (y - x < c) ans = t1.query(1, 1, n, x, y).mx;
			else {
				ans = max(t1.query(1, 1, n, x, x + c - 1).mx, t1.query(1, 1, n, y - c + 1, y).mx);
				if (by - bx > 1) {
					ans = max(ans, t3.query(1, 1, t, bx + 1, by - 1));
					if (by - bx > 2) ans = max(ans, t4.query(1, 1, t, bx + 2, by - 1));
					ans = max(ans, max(t2[bx + 1].query(1, 1, c, idx, c).mx, t2[by].query(1, 1, c, 1, idy).mx));
				} else ans = max(ans, t2[by].query(1, 1, c, idx, idy).mx);
			}
			printf("%lld\n", ans);
		}
	}
}