#include<bits/stdc++.h>

using namespace std;
using ll = long long;

struct Nd {
    ll s, p, q, m;
};

ll inf = (1LL << 60);

Nd mg(Nd a, Nd b) {
    Nd c;
    c.s = a.s + b.s;
    c.p = max(a.p, a.s + b.p);
    c.q = max(b.q, b.s + a.q);
    c.m = max(max(a.m, b.m), a.q + b.p);
    return c;
}

struct St {
    int n;
    vector<Nd> tr;

    St(int n = 0): n(n), tr(4 * n + 5) {}

    void bd(int id, int l, int r, vector<ll> &a) {
        if (l == r) {
            ll v = a[l];
            tr[id] = {v, v, v, v};
            return;
        }
        int m = (l + r) >> 1;
        bd(id << 1, l, m, a);
        bd(id << 1 | 1, m + 1, r, a);
        tr[id] = mg(tr[id << 1], tr[id << 1 | 1]);
    }

    Nd qr(int id, int l, int r, int ql, int rr) {
        if (ql <= l && r <= rr) return tr[id];
        int m = (l + r) >> 1;
        if (rr <= m) return qr(id << 1, l, m, ql, rr);
        if (ql > m) return qr(id << 1 | 1, m + 1, r, ql, rr);
        Nd a = qr(id << 1, l, m, ql, rr);
        Nd b = qr(id << 1 | 1, m + 1, r, ql, rr);
        return mg(a, b);
    }

    Nd qr(int l, int r) {
        return qr(1, 1, n, l, r);
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<ll> a(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];

        St st(n);
        st.bd(1, 1, n, a);

        int m;
        cin >> m;
        while (m--) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;

            ll ans = -inf;

            if (y1 < x2) {
                ll l1 = st.qr(x1, y1).q;
                ll md = 0;
                if (y1 + 1 <= x2 - 1) md = st.qr(y1 + 1, x2 - 1).s;
                ll r1 = st.qr(x2, y2).p;
                ans = l1 + md + r1;
            } else {
                if (x1 <= x2 - 1) {
                    ll l1 = st.qr(x1, x2 - 1).q;
                    ll r1 = st.qr(x2, y2).p;
                    ans = max(ans, l1 + r1);
                }

                ans = max(ans, st.qr(x2, y1).m);

                if (y1 + 1 <= y2) {
                    ll l2 = st.qr(x2, y1).q;
                    ll r2 = st.qr(y1 + 1, y2).p;
                    ans = max(ans, l2 + r2);
                }
            }

            cout << ans << "\n";
        }
    }

    return 0;
}