#include <bits/stdc++.h>
#define int long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid (l + r >> 1)

using namespace std;

const int maxn = 5e5 + 1;
const int inf = 1e11;

struct node {
    int tot;
    int pre;
    int suf;
    int mx;

    node(): tot(0), pre(-inf), suf(-inf), mx(-inf) {}
};

int t, n, q;
int a[maxn];
node tree[maxn << 2];

void clear() {
	memset(a, 0, sizeof(a));
	for (int i = 1; i < (maxn << 2); i++) {
		tree[i] = node();
	}
}

void pushup(int u) {
    tree[u].tot = tree[ls].tot + tree[rs].tot;
    tree[u].pre = max(tree[ls].pre, tree[ls].tot + tree[rs].pre);
    tree[u].suf = max(tree[rs].suf, tree[ls].suf + tree[rs].tot);
    tree[u].mx = max(max(tree[ls].mx, tree[rs].mx), tree[ls].suf + tree[rs].pre);
}

void build(int u, int l, int r) {
    if (l == r) {
        tree[u].tot = a[l];
        tree[u].pre = tree[u].suf = tree[u].mx = a[l];
        return;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u);
}

node query(int u, int l, int r, int lq, int rq) {
    if (lq <= l && r <= rq) {
        return tree[u];
    }
    node ld = node(), rd = node(), ans = node();
    if (lq <= mid) ld = query(ls, l, mid, lq, rq);
    if (rq > mid) rd = query(rs, mid + 1, r, lq, rq);
    ans.tot = ld.tot + rd.tot;
    ans.pre = max(ld.pre, ld.tot + rd.pre);
    ans.suf = max(rd.suf, ld.suf + rd.tot);
    ans.mx = max(max(ld.mx, rd.mx), ld.suf + rd.pre);
    pushup(u);
    return ans;
}

signed main() {
	cin >> t;
	while (t--) {
		clear();
		cin >> n;
	    for (int i = 1; i <= n; i++) {
	        cin >> a[i];
	    }
	    build(1, 1, n);
	    cin >> q;
	    for (int i = 1, l1, r1, l2, r2; i <= q; i++) {
        	cin >> l1 >> r1 >> l2 >> r2;
        	if (r1 <= l2) {
        		int ld = (l1 == r1 ? 0 : query(1, 1, n, l1, r1 - 1).suf);
        		int md = query(1, 1, n, r1, l2).tot;
        		int rd = (l2 == r2 ? 0 : query(1, 1, n, l2 + 1, r2).pre);
        		cout << ld + md + rd << endl;
			} else {
				int ld = query(1, 1, n, l1, l2).suf;
				int rd = (l2 == r2 ? 0 : query(1, 1, n, l2 + 1, r2).pre);
				int md = query(1, 1, n, l2, r1).mx;
				cout << max(md, ld + rd) << endl;
			}
	    }
	}
    return 0;
}