#include <bits/stdc++.h>
#define ls num << 1
#define rs ls | 1
#define li ls, l, mid
#define ri rs, mid + 1, r
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); }
char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<25],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
	for(;isdigit(ch);ch=getchar()) s=s*10+ch-'0';
	return s*w;
}
inline void print(ll x) {
	static char buf_num[20];
    int n = 0;
    do buf_num[n++] = x % 10 + '0'; while(x /= 10);
    while (n--) *O++=buf_num[n];
	*O++='\n';
}
// template <typename T> void writeln(T x) { print(x); *O++='\n'; }
const int N = 2e6 + 10;
int n, m, c, a[N], tot;
struct segment1 {
	struct seg {
		ll lans, rans, ans, sum;
		inline seg operator + (const seg& t) {
			return {max(lans, sum + t.lans), max(t.rans, t.sum + rans), max(max(ans, t.ans), rans + t.lans), sum + t.sum};
		}
	} t[4194304];
	inline void pushup(int num) {
		t[num] = t[ls] + t[rs];
	}
	inline void build(int num, int l, int r) {
		if (l == r) {
			t[num].sum = t[num].ans = t[num].lans = t[num].rans = a[l];
			return;
		} int mid = (l + r) >> 1;
		build(li); build(ri);
		pushup(num);
	}
	inline void modify(int num, int l, int r, int x, int y) {
		if (l == r) {
			t[num].sum = t[num].ans = t[num].lans = t[num].rans = y;
			// cout << l << " " << t[num].sum << endl;
			return;
		} int mid = (l + r) >> 1;
		if (mid >= x) modify(li, x, y);
		else modify(ri, x, y);
		pushup(num);
		// if (x == 22) cout << l << " " << r << " " << t[num].sum << endl;
	}
	inline seg query(int num, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			// cout << t[0].sum << endl;
			// cout << l << " " << r << " " << t[num].sum << " " << t[num].ans << endl;
			return t[num];
		}
		int mid = (l + r) >> 1;
		if (mid < L) return query(ri, L, R);
		if (mid >= R) return query(li, L, R);
		return query(li, L, R) + query(ri, L, R);
	}
} seg1;
struct segment2 {
	// int ls[N * 4], rs[N * 4], tot;
	// ll tag[2][N * 4];
	vector <array <int, 2>> tag;
	struct seg {
		ll ans, mx[2];
		inline seg operator + (const seg& t) {
			return {max(max(ans, t.ans), mx[0] + t.mx[1]), {max(mx[0], t.mx[0]), max(mx[1], t.mx[1])}};
		}
	};
	vector <seg> t;
	inline void resize(int mxn) {
		int N=1;
		while(N<=mxn) N<<=1;
		tag.resize(N<<1), t.resize(N<<1);
		return ;
	}
	inline void down(int k, int num, ll tt) {
		// cout << num << " " << tt << endl;
		tag[num][k] += tt;
		t[num].ans += tt;
		t[num].mx[k] += tt;
	}
	inline void pushdown(int num) {
		F(i, 0, 1)
			if (tag[num][i]) {
				down(i, ls, tag[num][i]);
				down(i, rs, tag[num][i]);
				tag[num][i] = 0;
			}
	}
	inline void modify(int num, int l, int r, int x, int y, ll z) {
		if (l == r) {
			t[num].mx[y] = z;
			t[num].ans = -1e18;
			return;
		} pushdown(num);
		int mid = (l + r) >> 1;
		if (mid >= x) modify(li, x, y, z);
		else modify(ri, x, y, z);
		t[num] = t[ls] + t[rs];
	}
	inline void change(int num, int l, int r, int L, int R, int x, int y) {
		if (L <= l && r <= R) {
			down(x, num, y);
			return;
		} pushdown(num);
		int mid = (l + r) >> 1;
		if (mid >= L) change(li, L, R, x, y);
		if (mid < R) change(ri, L, R, x, y);
		t[num] = t[ls] + t[rs];
	}
	inline seg query1(int num, int l, int r, int L, int R) {
		if (L <= l && r <= R) return t[num];
		pushdown(num);
		int mid = (l + r) >> 1;
		if (mid < L) return query1(ri, L, R);
		if (mid >= R) return query1(li, L, R);
		return query1(li, L, R) + query1(ri, L, R);
	}
	inline pair <ll, ll> query2(int num, int l, int r, int x) {
		if (l == r) return make_pair(-1e18, t[num].mx[1]);
		pushdown(num);
		int mid = (l + r) >> 1;
		if (mid >= x) {
			pair <ll, ll> tt = query2(li, x);
			return make_pair(tt.first, max(tt.second, t[rs].mx[1]));
		} pair <ll, ll> tt = query2(ri, x);
		return make_pair(max(tt.first, t[ls].mx[0]), tt.second);
	}
	inline ll query2(int num, int l, int r, int L, int R, int x) {
		if (L > R) return 0;
		if (L <= l && r <= R) return t[num].mx[x];
		pushdown(num);
		int mid = (l + r) >> 1;
		if (mid < L) return query2(ri, L, R, x);
		if (mid >= R) return query2(li, L, R, x);
		return max(query2(li, L, R, x), query2(ri, L, R, x));
	}
} seg[N];
struct segment3 {
	ll maxn[4194304];
	#define ls num << 1
	#define rs ls | 1
	inline void build(int num, int l, int r) {
		if (l == r) {
			maxn[num] = seg1.query(1, 1, n, (l - 1) * c + 1, l * c).ans;
			return;
		} int mid = (l + r) >> 1;
		build(li); build(ri);
		maxn[num] = max(maxn[ls], maxn[rs]);
	}
	inline void modify(int num, int l, int r, int x, ll y) {
		if (l == r) {
			maxn[num] = y;
			return;
		} int mid = (l + r) >> 1;
		if (mid >= x) modify(li, x, y);
		else modify(ri, x, y);
		maxn[num] = max(maxn[ls], maxn[rs]);
	}
	inline ll query(int num, int l, int r, int L, int R) {
		if (L > R) return 0;
		if (L <= l && r <= R) return maxn[num];
		int mid = (l + r) >> 1;
		if (mid < L) return query(ri, L, R);
		if (mid >= R) return query(li, L, R);
		return max(query(li, L, R), query(ri, L, R));
	}
} seg3, seg4;
signed main() {
	n = read(); m = read(); c = read();
	F(i, 1, n) a[i] = read();
	seg1.build(1, 1, n);
	tot = (n - 1) / c + 1;
	seg3.build(1, 1, tot);
	// F(i, 1, tot) seg3.modify(1, 1, tot, i, seg1.query(1, 1, n, l[i], r[i]).ans);
	// return 0;
	F(i, 1, tot - 1) {
		seg[i].resize(c);
		ll s = 0;
		int l1 = (i - 1) * c + 1, r1 = l1 + c - 1;
		DF(j, r1, l1) {
			s += a[j];
			seg[i].modify(1, 0, c, j - l1, 1, s);
		} s = 0;
		int l2 = r1 + 1, r2 = r1 + c;
		F(j, l2, r2) {
			s += a[j];
			seg[i].modify(1, 0, c, j - l2, 0, s);
		} seg4.modify(1, 1, tot, i, seg[i].t[1].ans);
	}
	F(_, 1, m) {
		int f = read(), x = read(), y = read();
		int numx = (x - 1) / c + 1, lx = (numx - 1) * c + 1, rx = numx * c;
		int numy = (y - 1) / c + 1, ly = (numy - 1) * c + 1, ry = numy * c;
		if (f == 1) {
			int k = y - a[x]; a[x] = y;
			seg1.modify(1, 1, n, x, a[x]);
			seg3.modify(1, 1, tot, numx, seg1.query(1, 1, n, lx, rx).ans);
			if (numx > 1) {
				seg[numx - 1].change(1, 0, c, x - lx, rx - lx, 0, k);
				seg4.modify(1, 1, tot, numx - 1, seg[numx - 1].t[1].ans);
			}
			if (numx < tot) {
				seg[numx].change(1, 0, c, 0, x - lx, 1, k);
				seg4.modify(1, 1, tot, numx, seg[numx].t[1].ans);
				// work2(numx);
			}
		} else {
			if (numx == numy) {
				print(max(0ll, seg1.query(1, 1, n, x, y).ans));
				continue;
			}
			ll ans = 0;
			chkmax(ans, seg1.query(1, 1, n, x, rx).ans);
			chkmax(ans, seg1.query(1, 1, n, ly, y).ans);
			if (numx + 1 == numy) {
				int l1 = x - lx;
				int l2 = 0, r2 = y - ly;
				if (l1 <= r2) {
					chkmax(ans, seg[numx].query1(1, 0, c, l1, r2).ans);
					pair <ll, ll> tmp = seg[numx].query2(1, 0, c, l1);
					chkmax(ans, tmp.first + tmp.second);
					tmp = seg[numx].query2(1, 0, c, r2 + 1);
					chkmax(ans, tmp.first + tmp.second);
				} else {
					chkmax(ans, seg[numx].query2(1, 0, c, l1, c, 1) + seg[numx].query2(1, 0, c, l2, r2, 0));
					// chkmax(ans, seg2.query2(rrt[numx], 0, c, max(l1, r2 + 1), r1, 1) + seg2.query2(rrt[numx], 0, c, l2, r2, 0));
				}
				print(ans);
				continue;
			}
			chkmax(ans, seg3.query(1, 1, tot, numx + 1, numy - 1));
			chkmax(ans, seg4.query(1, 1, tot, numx + 1, numy - 2));
			chkmax(ans, seg[numx].query1(1, 0, c, x - lx, c).ans);
			pair <ll, ll> tmp = seg[numx].query2(1, 0, c, x - lx);
			chkmax(ans, tmp.first + tmp.second);
			chkmax(ans, seg[numy - 1].query1(1, 0, c, 0, y - ly).ans);
			tmp = seg[numy - 1].query2(1, 0, c, y - ly + 1);
			chkmax(ans, tmp.first + tmp.second);
			print(ans);
		}
	} fwrite(obuf,O-obuf,1,stdout);
	return 0;
}