三分算法

#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
const int N = 200010;
ll a[N << 1], sum[N << 1];
int x, y, z;
int n, m, q;
ll js(int k) {
	return sum[k + z - 1] - sum[k - 1];
}
void work() {
	cin >> x >> y >> z;
	int l = n - x, r = n + y - z + 2;
	while (r - l > 8) {//三分算法
		int lmid = l + (r - l) / 3;
		int rmid = r - (r - l) / 3;
		if (js(lmid) <= js(rmid))l = lmid;
		else r = rmid;
	}
	ll ans = -2e15;
	for (int i = l+1;i < r;i++) {//区间足够小就直接算
		ans = max(ans, js(i));
	}
	cout << ans << endl;
}
void solve() {
	cin >> n >> m >> q;
	for (int i = 1;i <= n + m;i++)cin >> a[i];
	sort(a + 1, a + n + 1);
	sort(a + n + 1, a + n + m + 1, greater<int>());
	for (int i = 1;i <= n + m;i++)sum[i] = sum[i - 1] + a[i];
	while (q--) {
		work();
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T = 1;
	cin >> T;
	while (T--)solve();
	return 0;
}