#include <bits/stdc++.h>   using namespace std;   int rd() {     int x = 0, flg = 1;     char c = getchar();     for (; (c < 48 || c > 57) && c !=  - ; c = getchar())       ;     if (c ==  - ) flg = -1, c = getchar();     for (; c > 47 && c < 58; x = x * 10 + c - 48, c = getchar())       ;     return flg * x;   }   const int mxn = 100010;   struct nd {     int sm, px, py, sx, sy, mx, ml, mr, _px, _py, _sx, _sy, _mx, _ml, _mr;     nd operator!() {       return (nd){-sm, -_px, _py, -_sx, _sy, -_mx, _ml, _mr,                   -px, py,   -sx, sy,   -mx, ml,   mr};     }   } tr[mxn << 2], ret;   int tag[mxn << 2];   void mrg(nd x, nd y) {     ret.sm = x.sm + y.sm;     if (x.px < x.sm + y.px)       ret.px = x.px, ret.py = x.py;     else       ret.px = x.sm + y.px, ret.py = y.py;     if (y.sx < y.sm + x.sx)       ret.sx = y.sx, ret.sy = y.sy;     else       ret.sx = y.sm + x.sx, ret.sy = x.sy;     if (x.mx < y.mx)       if (x.mx < x.sx + y.px)         ret.mx = x.mx, ret.ml = x.ml, ret.mr = x.mr;       else         ret.mx = x.sx + y.px, ret.ml = x.sy, ret.mr = y.py;     else if (y.mx < x.sx + y.px)       ret.mx = y.mx, ret.ml = y.ml, ret.mr = y.mr;     else       ret.mx = x.sx + y.px, ret.ml = x.sy, ret.mr = y.py;     if (x._px > x.sm + y._px)       ret._px = x._px, ret._py = x._py;     else       ret._px = x.sm + y._px, ret._py = y._py;     if (y._sx > y.sm + x._sx)       ret._sx = y._sx, ret._sy = y._sy;     else       ret._sx = y.sm + x._sx, ret._sy = x._sy;     if (x._mx > y._mx)       if (x._mx > x._sx + y._px)         ret._mx = x._mx, ret._ml = x._ml, ret._mr = x._mr;       else         ret._mx = x._sx + y._px, ret._ml = x._sy, ret._mr = y._py;     else if (y._mx > x._sx + y._px)       ret._mx = y._mx, ret._ml = y._ml, ret._mr = y._mr;     else       ret._mx = x._sx + y._px, ret._ml = x._sy, ret._mr = y._py;   }   void mrg_rev(nd x, nd y) {     ret.sm = -x.sm - y.sm;     if (x._px > x.sm + y._px)       ret.px = -x._px, ret.py = x._py;     else       ret.px = -x.sm - y._px, ret.py = y._py;     if (y._sx > y.sm + x._sx)       ret.sx = -y._sx, ret.sy = y._sy;     else       ret.sx = -y.sm - x._sx, ret.sy = x._sy;     if (x._mx > y._mx)       if (x._mx > x._sx + y._px)         ret.mx = -x._mx, ret.ml = x._ml, ret.mr = x._mr;       else         ret.mx = -x._sx - y._px, ret.ml = x._sy, ret.mr = y._py;     else if (y._mx > x._sx + y._px)       ret.mx = -y._mx, ret.ml = y._ml, ret.mr = y._mr;     else       ret.mx = -x._sx - y._px, ret.ml = x._sy, ret.mr = y._py;     if (x.px < x.sm + y.px)       ret._px = -x.px, ret._py = x.py;     else       ret._px = -x.sm - y.px, ret._py = y.py;     if (y.sx < y.sm + x.sx)       ret._sx = -y.sx, ret._sy = y.sy;     else       ret._sx = -y.sm - x.sx, ret._sy = x.sy;     if (x.mx < y.mx)       if (x.mx < x.sx + y.px)         ret._mx = -x.mx, ret._ml = x.ml, ret._mr = x.mr;       else         ret._mx = -x.sx - y.px, ret._ml = x.sy, ret._mr = y.py;     else if (y.mx < x.sx + y.px)       ret._mx = -y.mx, ret._ml = y.ml, ret._mr = y.mr;     else       ret._mx = -x.sx - y.px, ret._ml = x.sy, ret._mr = y.py;   }   void pushup(int i) {     if (tag[i])       mrg_rev(tr[(i << 1)], tr[(i << 1 | 1)]);     else       mrg(tr[(i << 1)], tr[(i << 1 | 1)]);     tr[i] = ret;   }   void update(int i, int l, int r, int p, int v) {     if (l == r) {       tr[i] = (nd){v, v, l, v, l, v, l, l, v, l, v, l, v, l, l};       return;     }     if (p <= ((l + r) >> 1))       update((i << 1), l, ((l + r) >> 1), p, v);     else       update((i << 1 | 1), ((l + r) >> 1) + 1, r, p, v);     pushup(i);   }   void modify(int i, int l, int r, int x, int y) {     if (r < x || l > y) return;     if (l >= x && r <= y) {       tag[i] ^= 1, tr[i] = !tr[i];       return;     }     modify((i << 1), l, ((l + r) >> 1), x, y);     modify((i << 1 | 1), ((l + r) >> 1) + 1, r, x, y);     pushup(i);   }   int tot, id[mxn], fl[mxn], bl[mxn], br[mxn];   void query(int i, int l, int r, int x, int y, bool fg) {     if (r < x || l > y) return;     if (l >= x && r <= y) {       id[++tot] = i;       fl[tot] = fg;       bl[tot] = l, br[tot] = r;       return;     }     query((i << 1), l, ((l + r) >> 1), x, y, fg ^ tag[i]);     query((i << 1 | 1), ((l + r) >> 1) + 1, r, x, y, fg ^ tag[i]);   }   void qry() {     if (fl[1])       ret = !tr[id[1]];     else       ret = tr[id[1]];     for (int i = 2; i <= tot; ++i)       if (fl[i])         mrg(ret, !tr[id[i]]);       else         mrg(ret, tr[id[i]]);   }   int n, q, a[mxn], qi[mxn], ql[mxn], qr[mxn], qx[mxn], qy[mxn];   void build(int i, int l, int r) {     if (l == r) {       tr[i] =           (nd){a[l], a[l], l, a[l], l, a[l], l, l, a[l], l, a[l], l, a[l], l, l};       return;     }     build((i << 1), l, ((l + r) >> 1)),         build((i << 1 | 1), ((l + r) >> 1) + 1, r);     pushup(i);   }   int main() {     n = rd();     for (int i = 1; i <= n; ++i) a[i] = rd();     build(1, 1, n);     q = rd();     for (int i = 1; i <= q; ++i)       if (rd()) {         int l = rd(), r = rd(), k = rd(), m = 0, ans = 0;         tot = 0;         query(1, 1, n, l, r, 0);         for (; k--;) {           qry();           if (ret._mx <= 0) break;           ans += ret._mx;           int x = ret._ml, y = ret._mr;           modify(1, 1, n, x, y);           ql[++m] = x, qr[m] = y;         }         printf( %d n , ans);         for (int j = 1; j <= m; ++j) modify(1, 1, n, ql[j], qr[j]);       } else {         int x = rd(), y = rd();         update(1, 1, n, x, y);       }     return 0;   }   