线段树，高效

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

typedef long long ll;

const int INF = 2e9; // 定义一个足够大的数作为无穷大
const int MAXN = 100005; // 定义最大数组长度

// 定义线段树结构体，用于高效查询区间信息
struct SegmentTree {
    // 线段树的节点结构体，存储区间内的最小值、最大值、是否有零、最小正值和最大负值
    struct Node {
        int min_val, max_val;
        bool has_zero;
        int min_positive, max_negative;
        Node() : min_val(INF), max_val(-INF), has_zero(false), min_positive(INF), max_negative(-INF) {}
        Node(int val) : min_val(val), max_val(val), has_zero(val == 0) {
            min_positive = (val > 0) ? val : INF;  // 如果是正数，存储该值；否则存储INF
            max_negative = (val < 0) ? val : -INF;  // 如果是负数，存储该值；否则存储-INF
        }
    };

    vector<Node> tree;  // 线段树数组
    vector<int> *arr;    // 指向原始数组的指针

    // 构造函数，初始化线段树
    SegmentTree(vector<int> &a) {
        arr = &a;
        int n = a.size();
        tree.resize(4 * n);  // 线段树通常需要4倍空间
        build(1, 0, n - 1);  // 从根节点开始构建线段树
    }

    // 合并两个子节点的信息到父节点
    Node merge(const Node &a, const Node &b) {
        Node res;
        res.min_val = min(a.min_val, b.min_val);  // 合并最小值
        res.max_val = max(a.max_val, b.max_val);  // 合并最大值
        res.has_zero = a.has_zero || b.has_zero;  // 合并是否有零
        res.min_positive = min(a.min_positive, b.min_positive);  // 合并最小正值
        res.max_negative = max(a.max_negative, b.max_negative);  // 合并最大负值
        return res;
    }

    // 构建线段树
    void build(int node, int start, int end) {
        if (start == end) {  // 如果是叶子节点
            tree[node] = Node((*arr)[start]);  // 存储该节点的值
            return;
        }
        int mid = (start + end) / 2;
        build(2 * node, start, mid);      // 构建左子树
        build(2 * node + 1, mid + 1, end); // 构建右子树
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);  // 合并左右子树信息
    }

    // 查询区间[l, r]的信息
    Node query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {  // 如果查询区间与当前区间无交集
            return Node();  // 返回空节点
        }
        if (l <= start && end <= r) {  // 如果当前区间完全包含在查询区间内
            return tree[node];  // 返回当前节点的信息
        }
        int mid = (start + end) / 2;
        Node left = query(2 * node, start, mid, l, r);      // 查询左子树
        Node right = query(2 * node + 1, mid + 1, end, l, r); // 查询右子树
        return merge(left, right);  // 合并左右子树查询结果
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;
    vector<int> A(n), B(m);
    for (int i = 0; i < n; ++i) cin >> A[i];  // 读取数组A
    for (int i = 0; i < m; ++i) cin >> B[i];  // 读取数组B

    SegmentTree stA(A), stB(B);  // 构建线段树用于A和B数组

    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        --l1; --r1; --l2; --r2;  // 转换为0-based索引

        // 查询A数组区间[l1, r1]的信息
        auto nodeA = stA.query(1, 0, n - 1, l1, r1);
        // 查询B数组区间[l2, r2]的信息
        auto nodeB = stB.query(1, 0, m - 1, l2, r2);

        ll res = -1e18;  // 初始化结果为负无穷
        vector<int> candidates;  // 存储候选的A值

        // 添加可能的候选值
        if (nodeA.max_val != -INF) candidates.push_back(nodeA.max_val);  // 最大值
        if (nodeA.min_val != INF) candidates.push_back(nodeA.min_val);   // 最小值
        if (nodeA.min_positive != INF) candidates.push_back(nodeA.min_positive);  // 最小正值
        if (nodeA.max_negative != -INF) candidates.push_back(nodeA.max_negative); // 最大负值
        if (nodeA.has_zero) candidates.push_back(0);  // 零

        // 去重
        sort(candidates.begin(), candidates.end());
        candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());

        // 遍历所有候选值，计算得分
        for (int a : candidates) {
            ll temp;
            if (a > 0) {
                temp = (ll)a * nodeB.min_val;  // 如果A值为正，乘以B的最小值
            } else if (a < 0) {
                temp = (ll)a * nodeB.max_val;  // 如果A值为负，乘以B的最大值
            } else {
                temp = 0;  // 如果A值为零，得分为零
            }
            res = max(res, temp);  // 更新最大得分
        }

        cout << res << '\n';  // 输出结果
    }

    return 0;
}