#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; ++i)
#define Rep(i, a, b) for (int i = a; i >= b; --i)
using namespace std;
namespace io {
template<typename T>inline void read(T &x) {
  char ch, f = 0; x = 0;
  while (!isdigit(ch = getchar())) f |= ch == '-';
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  x = f? -x: x;
}
char ch[40];
template<typename T>inline void write(T x) {
  (x < 0) && (putchar('-'), x = -x);
  x || putchar('0');
  int i = 0;
  while (x) ch[i++] = x % 10 ^ 48, x /= 10;
  while (i) putchar(ch[--i]);
}
}
#define rd io::read
#define wt io::write
using i64 = long long;
const int maxN = 2e6 + 5;
int a[maxN], c, n, blo, m;
struct Node1 {
  i64 sum, pre, suf, ans;
  Node1 operator+ (const Node1 &a) const {
    return {sum + a.sum, max(pre, sum + a.pre), max(a.suf, a.sum + suf), max({ans, a.ans, suf + a.pre})};
  }
};
struct Seg1 {
  vector<Node1> T;
  int len, beg;
  inline void init(int l) { len = l; T.resize(l << 2|1); }
  void build(int k, int l, int r) {
    if (l == r) {
      T[k].sum = a[beg + l - 1];
      T[k].ans = T[k].suf = T[k].pre = max(0, a[beg + l - 1]);      
      return;   
    }
    int mid = l + r >> 1;
    build(k << 1, l, mid);
    build(k << 1|1, mid + 1, r);
    T[k] = T[k << 1] + T[k << 1|1];
  }
  void update(int x, int v, int k, int l, int r) {
    if (l == r) {
      T[k].sum = v;
      T[k].ans = T[k].suf = T[k].pre = max(0, v);
      return;
    }
    int mid = l + r >> 1;
    if (x <= mid) update(x, v, k << 1, l, mid);
    else update(x, v, k << 1|1, mid + 1, r);
    T[k] = T[k << 1] + T[k << 1|1];
  }
  Node1 query(int x, int y, int k, int l, int r) {
    if (x <= l && r <= y) return T[k];
    int mid = l + r >> 1;
    if (x <= mid) {
      if (y > mid) return query(x, y, k << 1, l, mid) + query(x, y, k << 1|1, mid + 1, r);
      return query(x, y, k << 1, l, mid);
    }
    return query(x, y, k << 1|1, mid + 1, r);
  }
};
int bel[maxN], R[maxN];
struct Node2 {
  i64 sa, sb, pa, pb, ans;
  Node2 operator+ (const Node2 &a) const {
    return {sa + a.sa, sb + a.sb, max(pa, sa + a.pa), max(pb, sb + a.pb), max({ans + a.sb, a.ans + sa, pa + a.pb})};
  }
};
struct Seg2 {
  vector<Node2> T;
  int len, beg;
  inline void init(int l) { len = l; T.resize(l << 2|1); }
  void build(int k, int l, int r) {
    if (l == r) {
      T[k].sa = a[min(beg + l - 1 + c, n + 1)];
      T[k].sb = a[beg + l - 1];
      T[k].pa = max(T[k].sa, 0ll);
      T[k].pb = max(T[k].sb, 0ll);
      T[k].ans = max(T[k].pa, T[k].pb);
      return;
    }
    int mid = l + r >> 1;
    build(k << 1, l, mid);
    build(k << 1|1, mid + 1, r);
    T[k] = T[k << 1] + T[k << 1|1];
  }
  Node2 query(int x, int y, int op, int k, int l, int r) {
    if (x <= l && r <= y) return T[k];
    if (x > r || y < l) {
      Node2 r = T[k]; r.ans = -1e18;
      if (op) r.pa = -1e18;
      else r.pb = -1e18;
      return r;
    }
    int mid = l + r >> 1;
    return query(x, y, op, k << 1, l, mid) + query(x, y, op, k << 1|1, mid + 1, r);
  }
  i64 Squery(int x, int y, int op) {
    i64 v = query(x, y, op, 1, 1, len).ans;
    return v;
  }
  void update(int x, int op, int v, int k, int l, int r) {
    if (l == r) {
      if (op == 0) {
        T[k].sa = v; T[k].pa = max(T[k].sa, 0ll);
      } else {
        T[k].sb = v; T[k].pb = max(T[k].sb, 0ll);
      }
      T[k].ans = max(T[k].pa, T[k].pb);
      return;
    }
    int mid = l + r >> 1;
    if (x <= mid) update(x, op, v, k << 1, l, mid);
    else update(x, op, v, k << 1|1, mid + 1, r);
    T[k] = T[k << 1] + T[k << 1|1];
  }
};
vector<Seg1> T1;
vector<Seg2> T2;
vector<i64> mx, sx;
int lf[maxN];
void bbuild(int k = 1, int l = 1, int r = blo - 1) {
  if (l == r) {
    lf[l] = k;
    sx[k] = T2[l].T[1].ans;
    return;
  }
  int mid = l + r >> 1;
  bbuild(k << 1, l, mid);
  bbuild(k << 1|1, mid + 1, r);
  sx[k] = max(sx[k << 1], sx[k << 1|1]);
}
inline void uupdate(int x) {
  sx[lf[x]] = T2[x].T[1].ans;
  x = lf[x] >> 1;
  while (x) {
    sx[x] = max(sx[x << 1], sx[x << 1|1]); x >>= 1;
  }
}
i64 qqu(int x, int y, int k = 1, int l = 1, int r = blo - 1) {
  if (x <= l && r <= y) return sx[k];
  int mid = l + r >> 1; i64 ans = 0;
  if (x <= mid) ans = max(ans, qqu(x, y, k << 1, l, mid));
  if (y > mid) ans = max(ans, qqu(x, y, k << 1|1, mid + 1, r));
  return ans;
}
void build(int k = 1, int l = 1, int r = blo) {
  if (l == r) {
    if (l < blo) {
      T1[l].init(c); T2[l].init(c);
      T1[l].beg = T2[l].beg = (l - 1) * c + 1;
      T2[l].build(1, 1, c);
    } else {
      T1[l].init(n - (l - 1) * c);
      T1[l].beg = (l - 1) * c + 1;
    }
    T1[l].build(1, 1, T1[l].len);
    mx[k] = T1[l].T[1].ans;
    return;
  }
  int mid = l + r >> 1;
  build(k << 1, l, mid);
  build(k << 1|1, mid + 1, r);
  mx[k] = max(mx[k << 1], mx[k << 1|1]);
}
void update(int x, int v, int k = 1, int l = 1, int r = blo) {
  if (l == r) {
    int rr = x - R[l - 1];
    T1[l].update(rr, v, 1, 1, T1[l].len);
    if (l > 1) {
      T2[l - 1].update(rr, 0, v, 1, 1, T2[l - 1].len);
      uupdate(l - 1);
    }
    if (l < bel[n]) {
      T2[l].update(rr, 1, v, 1, 1, T2[l].len);
      uupdate(l);
    }
    mx[k] = T1[l].T[1].ans;
    return;
  }
  int mid = l + r >> 1;
  if (bel[x] <= mid) update(x, v, k << 1, l, mid);
  else update(x, v, k << 1|1, mid + 1, r);
  mx[k] = max(mx[k << 1], mx[k << 1|1]);
}
i64 query(int x, int y, int k = 1, int l = 1, int r = blo) {
  if (x <= l && r <= y) return mx[k];
  int mid = l + r >> 1; i64 ans = 0;
  if (x <= mid) ans = max(ans, query(x, y, k << 1, l, mid));
  if (y > mid) ans = max(ans, query(x, y, k << 1|1, mid + 1, r));
  return ans;
}
inline int gv(int x) { return x - R[bel[x] - 1]; }
i64 ask(int x, int y) {
  if (bel[x] == bel[y]) 
    return T1[bel[x]].query(gv(x), gv(y), 1, 1, R[bel[x]] - R[bel[x] - 1]).ans;
  if (y - x + 1 <= c) {
    Node1 p = T1[bel[x]].query(gv(x), T1[bel[x]].len, 1, 1, T1[bel[x]].len) + T1[bel[y]].query(1, gv(y), 1, 1, T1[bel[y]].len);
    return p.ans;
  }
  if (bel[y] == bel[x] + 1) {
    Node1 p;
    if (x > R[bel[x] - 1] + 1) p = T1[bel[x]].query(gv(x), T1[bel[x]].len, 1, 1, T1[bel[x]].len) + T1[bel[x + c - 1]].query(1, gv(x + c - 1), 1, 1, T1[bel[y]].len);
    else p = T1[bel[x]].T[1];
    i64 ans = max(p.ans, T1[bel[y]].query(1, gv(y), 1, 1, T1[bel[y]].len).ans);
    return max(ans, T2[bel[x]].Squery(gv(x + c), gv(y), 0));
  }
  i64 ans = max({query(bel[x] + 1, bel[y] - 1), T1[bel[x]].query(gv(x), T1[bel[x]].len, 1, 1, T1[bel[x]].len).ans, T1[bel[y]].query(1, gv(y), 1, 1, T1[bel[y]].len).ans});
  if (bel[y] - bel[x] > 2) ans = max(ans, qqu(bel[x] + 1, bel[y] - 2));
  ans = max({ans, T2[bel[x]].Squery(gv(x), c, 0), T2[bel[y] - 1].Squery(1, gv(y), 1)});
  return ans;
}
int main() {
  rd(n); rd(m); rd(c);
  blo = (n - 1) / c + 1;
  For (i, 1, n) {
    rd(a[i]);
    bel[i] = (i - 1) / c + 1;
  }
  For (i, 1, blo) 
    R[i] = min(R[i - 1] + c, n);
  T1.resize(blo + 1); T2.resize(blo + 1); mx.resize(blo << 2|1); sx.resize(blo << 2|1);
  build(); bbuild();
  int op, x, y; 
  For (i, 1, m) {
    rd(op); rd(x); rd(y);
    if (op == 1) {
      update(x, y);
    } else {
      wt(ask(x, y)); putchar('\n');
    }
  }
  return 0;
}