#include <bits/stdc++.h>
// #include <bits/extc++.h>
using namespace std;

#define ll long long
#define ul unsigned ll
#define LL __int128_t
#define db double
#define DB long db
#define pii pair<int, int>
#define fi first
#define se second
#define mkpr make_pair
#define vi vector<int>
#define vii vector<pii>
#define rsz resize
#define ep emplace
#define pb pop_back
#define eb emplace_back
#define all(c) (c).begin(), (c).end()
#define bit(k) (1 << (k))
#define Bit(k) (1ll << (k))
#define BIT(k) ((LL)1 << (k))
#define lowbit(x) ((x) & -(x))
#define bin(s, k) ((s) >> (k) & 1)
#define lg2(x) (31 - __builtin_clz(x))
#define LG2(x) (63 - __builtin_clzll(x))
#define highbit(x) bit(lg2(x))
#define highbitll(x) Bit(LG2(x))
#define popcnt(x) __builtin_popcount(x)
#define mem(a, x) memset(a, x, sizeof(a))
#define req(i, l, r) for (int i(l), i##End(r); i < i##End; i = -~i)
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)
#define per(i, r, l) for (int i(r), i##End(l); i >= i##End; i = ~-i)

// #define FILERR

#ifdef JYR
#include "debug.h"
#define errm(x, ...) fprintf(stderr, x, ##__VA_ARGS__)
#define errs(x, ...) errm(x "\n", ##__VA_ARGS__)
#else
#define dbg(...) (__VA_ARGS__)
#define dbgArr(...) (__VA_ARGS__)
#define errm(x, ...) (x, ##__VA_ARGS__)
#define errs(x, ...) (x, ##__VA_ARGS__)
#endif

#define __

template<typename T, typename U> void chkmx(T &_a, U _b) { if (_a < _b) _a = _b; }
template<typename T, typename U> void chkmn(T &_a, U _b) { if (_b < _a) _a = _b; }

#define vll vector<ll>

// #define MC

#define N 250005
#define mod 998244353
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

struct Info {
    ll mx, ml, mr, su;
    Info() {}
    Info(ll x) { mx = ml = mr = su = x; }
    Info(ll _mx, ll _ml, ll _mr, ll _su)
     : mx(_mx), ml(_ml), mr(_mr), su(_su) {}
};

Info operator+(Info a, Info b) {
    return Info(max({a.mx, b.mx, a.mr + b.ml}),
                max(a.ml, a.su + b.ml),
                max(a.mr + b.su, b.mr),
                a.su + b.su);
}

int n, q;
ll a[N], b[N];
ll A[N], B[N];
pii L[N], R[N];
int st[N], tp;
int f[N], g[N];
ll mx[21][N];
struct node {
    int o, l, r, x, i;
    node() {}
    node(int _o, int _l, int _r, int _x, int _i = 0)
     : o(_o), l(_l), r(_r), x(_x), i(_i) {}
}; vector<node> V;
ll ans[N];

struct SegTree {
    #define lc (i << 1)
    #define rc (lc | 1)
    
    Info vl[N << 2];
    
    void psu(int i) { vl[i] = vl[lc] + vl[rc]; }
    
    void bld(int i = 1, int l = 1, int r = n) {
        if (l == r) { vl[i] = Info(a[l]); return; }
        int t = (l + r) >> 1; bld(lc, l, t), bld(rc, t + 1, r);
        return psu(i);
    }
    
    Info qry(int u, int v, int i = 1, int l = 1, int r = n) {
        if (u <= l && r <= v) return vl[i];
        int t = (l + r) >> 1;
        if (v <= t) return qry(u, v, lc, l, t);
        if (t < u) return qry(u, v, rc, t + 1, r);
        return qry(u, v, lc, l, t) + qry(u, v, rc, t + 1, r);
    }
} T;

struct STree {
    ll su[N << 2], ct[N << 2], tg[N << 2];
    
    void psu(int i) { su[i] = su[lc] + su[rc], ct[i] = ct[lc] + ct[rc]; }
    void chg(int i, ll k) { su[i] += ct[i] * k, tg[i] += k; }
    void psd(int i) { if (ll &k = tg[i]; k) chg(lc, k), chg(rc, k), k = 0; }
    
    void mdf(int u, int v, int k, int i = 1, int l = 1, int r = n) {
        if (u <= l && r <= v) return chg(i, k);
        int t = (l + r) >> 1; psd(i);
        if (u <= t) mdf(u, v, k, lc, l, t);
        if (t < v) mdf(u, v, k, rc, t + 1, r);
        return psu(i);
    }
    
    void mdg(int p, int k, int i = 1, int l = 1, int r = n) {
        if (l == r) { ct[i] += k; return; }
        int t = (l + r) >> 1; psd(i);
        p <= t ? mdg(p, k, lc, l, t) : mdg(p, k, rc, t + 1, r);
        return psu(i);
    }
    
    ll qry(int u, int v, int i = 1, int l = 1, int r = n) {
        if (u <= l && r <= v) return su[i];
        int t = (l + r) >> 1; psd(i); ll res = 0;
        if (u <= t) res += qry(u, v, lc, l, t);
        if (t < v) res += qry(u, v, rc, t + 1, r);
        return res;
    }
} S;

ll qry(int l, int r) {
    int k = lg2(r - l + 1);
    return max(mx[k][l], mx[k][r - bit(k) + 1]);
}

vll maxsum(vi _a, vi _b, vi _l1, vi _r1, vi _l2, vi _r2) {
    // rd(n, q);
    // rep(i, 1, n) rd(a[i], b[i]);
    n = _a.size(), q = _l1.size();
    rep(i, 1, n) a[i] = _a[i - 1], b[i] = _b[i - 1];
    rep(i, 1, n) A[i] = A[i - 1] + a[i];
    rep(i, 1, n) B[i] = B[i - 1] + b[i];
    ll t = 0;
    rep(i, 2, n) {
        if (A[i - 1] - t > 0) L[i].fi = -1;
        chkmn(t, A[i - 1]);
    }
    t = A[n];
    per(i, n - 1, 1) {
        if (t - A[i] > 0) R[i].fi = -1;
        chkmx(t, A[i]);
    }
    st[tp = 0] = n + 1;
    per(i, n, 0) {
        while (tp && B[st[tp]] >= B[i]) tp--;
        f[i + 1] = st[tp] - 1, st[++tp] = i;
    }
    reverse(B, B + n + 1), st[tp = 0] = n + 1;
    per(i, n, 0) {
        while (tp && B[st[tp]] <= B[i]) tp--;
        g[i + 1] = st[tp] - 1, st[++tp] = i;
    } reverse(B, B + n + 1), reverse(g + 1, g + n + 1);
    rep(i, 1, n) g[i] = n + 1 - g[i];
    rep(i, 1, n) if (~L[i].fi) L[i].se = max(f[i], i);
    rep(i, 1, n) if (~R[i].fi) R[i].fi = min(g[i], i);
    rep(i, 1, n) mx[0][i] = B[i];
    rep(k, 1, 20) rep(i, 1, n - bit(k) + 1)
        mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + bit(k - 1)]);
    T.bld();
    rep(i, 1, n) if (~L[i].fi) {
        ll X = i == 1 ? -INF : T.qry(1, i - 1).mx;
        int l = i, r = n, k = n + 1;
        while (l <= r) {
            int x = (l + r) >> 1;
            qry(i, x) - B[i - 1] >= X ? k = x, r = x - 1 : l = x + 1;
        } L[i].fi = k;
    }
    rep(i, 1, n) mx[0][i] = -B[i - 1];
    rep(k, 1, 20) rep(i, 1, n - bit(k) + 1)
    mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + bit(k - 1)]);
    rep(i, 1, n) if (~R[i].fi) {
        ll X = i == n ? -INF : T.qry(i + 1, n).mx;
        int l = 1, r = i, k = 0;
        while (l <= r) {
            int x = (l + r) >> 1;
            B[i] + qry(x, i) >= X ? k = x, l = x + 1 : r = x - 1;
        } R[i].se = k;
    }
    rep(i, 1, n) if (~L[i].fi && L[i].fi <= L[i].se) V.eb(0, i, i, L[i].fi), V.eb(4, i, i, L[i].se);
    rep(i, 1, n) if (~R[i].fi && R[i].fi <= R[i].se) V.eb(1, R[i].fi, R[i].se, i);
    rep(i, 1, q) {
        int l, r, u, v;
        // rd(l, r, u, v);
        l = _l1[i - 1], r = _r1[i - 1], u = _l2[i - 1], v = _r2[i - 1];
        l++, r++, u++, v++;
        V.eb(2, l, r, u - 1, i), V.eb(3, l, r, v, i);
    }
    sort(all(V), [](node i, node j) { return mkpr(i.x, i.o) < mkpr(j.x, j.o); });
    for (auto [o, l, r, x, i] : V) switch (o) {
        case 0: S.mdg(l, 1); break;
        case 1: S.mdf(l, r, 1); break;
        case 2: ans[i] -= S.qry(l, r); break;
        case 3: ans[i] += S.qry(l, r); break;
        default: S.mdg(l, -1);
    }
    // rep(i, 1, q) prs(ans[i]);
    vll _ans;
    rep(i, 1, q) _ans.eb(ans[i]);
    return _ans;
}