题目描述

给定数组 $A$、$B$，矩阵 $C_{ij}=A_iB_j$。每轮小 L 先在 $A$ 的给定区间选 $x$，小 Q 再在 $B$ 的给定区间选 $y$；小 L 最大化、小 Q 最小化 $C_{xy}$。求最优得分。

输入格式

第一行输入 $n,m,q$。第二行 $n$ 个整数 $A_i$，第三行 $m$ 个整数 $B_i$。接下来 $q$ 行每行四个整数 $l_1,r_1,l_2,r_2$。

输出格式

输出 $q$ 行，每行一个整数，表示该轮最优得分。

3 2 2
0 1 -2
-3 4
1 3 1 2
2 3 2 2

0
4

6 4 5
3 -1 -2 1 2 0
1 2 -1 -3
1 6 1 4
1 5 1 4
1 4 1 2
2 6 3 4
2 5 2 3

0
-2
3
2
-1

数据范围与提示

• $1 \le n,m,q \le 10^5$，$-10^9 \le A_i,B_i \le 10^9$。

来源

CSP-S 2022 T2