https://www.luogu.com.cn/record/92895471

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5, inf = 2.1e9 + 5;
ll n, m, q, l1, r1, l2, r2, a[N], b[N], lg[N], cnt1[N], cnt2[N], cnt3[N], cnt4[N], cnt5[N], cnt6[N];
ll f1[N][20], f2[N][20], f3[N][20], f4[N][20];
ll f5[N][20], f6[N][20], f7[N][20], f8[N][20];
// f1 max f2 min f3 max f4 min
int main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		f1[i][0] = f3[i][0] = -inf, f2[i][0] = f4[i][0] = inf;
		if (a[i] >= 0) f1[i][0] = f2[i][0] = a[i];
		if (a[i] <= 0) f3[i][0] = f4[i][0] = a[i];
	}
	for (int i = 1; i <= m; i ++) {
		cin >> b[i];
		f5[i][0] = f7[i][0] = -inf, f6[i][0] = f8[i][0] = inf;
		if (b[i] >= 0) f5[i][0] = f6[i][0] = b[i];
		if (b[i] <= 0) f7[i][0] = f8[i][0] = b[i];
	}
	for (int i = 2; i <= n; i ++) lg[i] = lg[i >> 1] + 1;
	for (int j = 1; j <= lg[n]; j ++)
		for (int i = 1; i + (1 << j) - 1 <= n; i ++) {
			f1[i][j] = max(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]);
			f2[i][j] = min(f2[i][j - 1], f2[i + (1 << (j - 1))][j - 1]);
			f3[i][j] = max(f3[i][j - 1], f3[i + (1 << (j - 1))][j - 1]);
			f4[i][j] = min(f4[i][j - 1], f4[i + (1 << (j - 1))][j - 1]);
		}
	for (int j = 1; j <= lg[m]; j ++)
		for (int i = 1; i + (1 << j) - 1 <= m; i ++) {
			f5[i][j] = max(f5[i][j - 1], f5[i + (1 << (j - 1))][j - 1]);
			f6[i][j] = min(f6[i][j - 1], f6[i + (1 << (j - 1))][j - 1]);
			f7[i][j] = max(f7[i][j - 1], f7[i + (1 << (j - 1))][j - 1]);
			f8[i][j] = min(f8[i][j - 1], f8[i + (1 << (j - 1))][j - 1]);
		}
	for (int i = 1; i <= q; i ++) {
        cin >> l1 >> r1 >> l2 >> r2;
    	ll k1 = lg[r1 - l1 + 1], p1 = 1 << k1;
    	ll k2 = lg[r2 - l2 + 1], p2 = 1 << k2;
    	ll apmax = max(f1[l1][k1], f1[r1 - p1 + 1][k1]);
    	ll apmin = min(f2[l1][k1], f2[r1 - p1 + 1][k1]);
   		ll anmax = max(f3[l1][k1], f3[r1 - p1 + 1][k1]);
    	ll anmin = min(f4[l1][k1], f4[r1 - p1 + 1][k1]);
		ll bpmax = max(f5[l2][k2], f5[r2 - p2 + 1][k2]);
    	ll bpmin = min(f6[l2][k2], f6[r2 - p2 + 1][k2]);
    	ll bnmax = max(f7[l2][k2], f7[r2 - p2 + 1][k2]);
    	ll bnmin = min(f8[l2][k2], f8[r2 - p2 + 1][k2]);
        if (bnmin == inf) {
        	if (apmin == inf) cout << anmax * bpmax << '\n';
        	else cout << apmax * bpmin << '\n';
		} else if (bpmin == inf) {
			if (anmin == inf) cout << apmin * bnmin << '\n';
			else cout << anmin * bnmax << '\n';
		} else if (anmin == inf) {
			if (bnmin == inf) cout << apmax * bpmin << '\n';
			else cout << apmin * bnmin << '\n';
		}
		else if (apmin == inf) {
			if (bpmin == inf) cout << anmin * bnmax << '\n';
			else cout << anmax * apmax << '\n';
		} else cout << max(apmin * bnmin, anmax * bpmax) << '\n';
    }
    return 0;
}