该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定长度为 $n$ 的数组 $A$ 和长度为 $m$ 的数组 $B$。每轮给出两个下标区间，小 L 先从 $A$ 区间选 $A_x$，小 Q 看见后从 $B$ 区间选 $B_y$。得分为 $A_xB_y$；小 L 希望最大化，小 Q 希望最小化。求双方均采用最优策略时每轮的得分。

输入格式

从 game.in 读入。第一行 $n,m,q$；第二行 $n$ 个 $A_i$；第三行 $m$ 个 $B_i$；接下来 $q$ 行各有 $l_1,r_1,l_2,r_2$。

输出格式

向 game.out 输出 $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

说明/提示

原题另有附件样例 3、4。$1\le n,m,q\le10^5$，$-10^9\le A_i,B_i\le10^9$。

性质 1：所有 $A_i,B_i>0$。性质 2：每轮有 $l_1=r_1$ 或 $l_2=r_2$。