20XX年国际信息学奥林匹克竞赛新增了混合项目。在混合项目中，由一名男学生和一名女学生组成一个团队来解决问题。信息学奥林匹克委员会为了组建参加混合项目的代表队，选拔了 $N$ 名男学生候选人和 $M$ 名女学生候选人。$N$ 名男学生候选人的编号从 $0$ 到 $N-1$。同样地，$M$ 名女学生候选人的编号从 $0$ 到 $M-1$。

团队的实力受组成团队的两名学生的构思能力和实现能力共同影响。学生的构思能力和实现能力可以用 $1$ 到 $10^9$ 之间的整数表示。$i$ 号男学生的构思能力为 $A_1[i]$，实现能力为 $B_1[i]$。此外，$j$ 号女学生的构思能力为 $A_2[j]$，实现能力为 $B_2[j]$。如果 $i$ 号男学生和 $j$ 号女学生组成一个团队，该团队的实力定义为 $(A_1[i] + A_2[j]) \times (B_1[i] + B_2[j])$。

由于学生们都是经过激烈竞争选拔出来的候选人，不存在某位学生在构思能力和实现能力上都优于另一位学生的情况。更准确地说，男学生的构思能力随编号增大而增加，实现能力随编号增大而减少。即对于 $0 \le i \le N-2$，满足 $A_1[i] < A_1[i+1]$ 且 $B_1[i] > B_1[i+1]$。同样地，女学生的构思能力也随编号增大而增加，实现能力随编号增大而减少。即对于 $0 \le j \le M-2$，满足 $A_2[j] < A_2[j+1]$ 且 $B_2[j] > B_2[j+1]$。

信息学奥林匹克委员会希望根据不同的场景组建团队，使得团队实力最大化。存在 $Q$ 个场景，编号从 $0$ 到 $Q-1$。在 $k$ 号场景中，男学生的编号必须在 $L_1[k]$ 到 $R_1[k]$ 之间，女学生的编号必须在 $L_2[k]$ 到 $R_2[k]$ 之间。请编写一个程序，求出每个场景下满足条件且能构成的团队实力的最大值。

实现细节

你需要实现以下函数：

vector<long long> build_teams(vector<int> A1, vector<int> B1, vector<int> A2,
vector<int> B2, vector<int> L1, vector<int> R1, vector<int> L2, vector<int> R2)

• $A_1, B_1$: 长度为 $N$ 的数组。$i$ 号男学生的构思能力为 $A_1[i]$，实现能力为 $B_1[i]$。($0 \le i \le N-1$)
• $A_2, B_2$: 长度为 $M$ 的数组。$j$ 号女学生的构思能力为 $A_2[j]$，实现能力为 $B_2[j]$。($0 \le j \le M-1$)
• $L_1, R_1, L_2, R_2$: 长度为 $Q$ 的数组。在 $k$ 号场景中，男学生的编号必须在 $L_1[k]$ 到 $R_1[k]$ 之间，女学生的编号必须在 $L_2[k]$ 到 $R_2[k]$ 之间。($0 \le k \le Q-1$)
• 该函数必须返回一个大小为 $Q$ 的数组 $C$。$C[k]$ 应等于 $k$ 号场景下能构成的团队实力的最大值。

提交的源代码中不得执行任何输入输出函数。

数据范围

• $1 \le N \le 100\,000$
• $1 \le M \le 100\,000$
• 对于所有 $0 \le i \le N-1$，有 $1 \le A_1[i], B_1[i] \le 10^9$
• 对于所有 $0 \le j \le M-1$，有 $1 \le A_2[j], B_2[j] \le 10^9$
• 对于所有 $0 \le i \le N-2$，有 $A_1[i] < A_1[i+1]$，$B_1[i] > B_1[i+1]$
• 对于所有 $0 \le j \le M-2$，有 $A_2[j] < A_2[j+1]$，$B_2[j] > B_2[j+1]$
• $1 \le Q \le 100\,000$
• 对于所有 $0 \le k \le Q-1$，有 $0 \le L_1[k] \le R_1[k] \le N-1$
• 对于所有 $0 \le k \le Q-1$，有 $0 \le L_2[k] \le R_2[k] \le M-1$

子任务

1. (5分) $N \le 500, M \le 500, Q \le 500$
2. (10分) $Q \le 20$
3. (10分) 对于所有 $0 \le k \le Q-1$，有 $L_2[k] = 0, R_2[k] = M-1$
4. (35分) 对于所有 $0 \le k \le Q-1$，有 $L_2[k] = R_2[k]$
5. (40分) 无额外限制

样例

样例 1

输入数据：

N = 5, M = 4, A1 = [2, 7, 8, 9, 10], B1 = [10, 9, 8, 6, 1], A2 = [1, 3, 5, 9], B2 = [10, 8, 7, 5], Q = 3,
L1 = [0, 2, 1], R1 = [4, 3, 1], L2 = [1, 0, 0], R2 = [3, 2, 0]

评测程序调用如下：

build_teams([2, 7, 8, 9, 10], [10, 9, 8, 6, 1], [1, 3, 5, 9], [10, 8, 7, 5],
[0, 2, 1], [4, 3, 1], [1, 0, 0], [3, 2, 0])

在 0 号场景中，男学生编号为 0 到 4，女学生编号为 1 到 3。选择 1 号男学生和 3 号女学生，团队实力为 $(7+9) \times (9+5) = 224$。这是满足条件下的最大值。

在 1 号场景中，男学生编号为 2 到 3，女学生编号为 0 到 2。选择 2 号男学生和 2 号女学生，团队实力为 $(8+5) \times (8+7) = 195$。这是满足条件下的最大值。

在 2 号场景中，男学生编号为 1，女学生编号为 0。团队实力为 $(7+1) \times (9+10) = 152$。

因此，函数应返回 [224, 195, 152]。

样例 2

输入数据：

N = 4, M = 2, A1 = [1, 6, 8, 10], B1 = [9, 5, 3, 1], A2 = [5, 6], B2 = [8, 7], Q = 4, L1 = [0, 1, 2, 3],
R1 = [0, 1, 2, 3], L2 = [0, 0, 0, 0], R2 = [1, 1, 1, 1]

评测程序调用如下：

build_teams([1, 6, 8, 10], [9, 5, 3, 1], [5, 6], [8, 7], [0, 1, 2, 3], [0, 1,
2, 3], [0, 0, 0, 0], [1, 1, 1, 1])

在 0 号场景中，选择 0 号男学生和 1 号女学生，团队实力为 $(1+6) \times (9+7) = 112$。 在 1 号场景中，选择 1 号男学生和 1 号女学生，团队实力为 $(6+6) \times (5+7) = 144$。 在 2 号场景中，选择 2 号男学生和 0 号女学生，团队实力为 $(8+5) \times (3+8) = 143$。 在 3 号场景中，选择 3 号男学生和 0 号女学生，团队实力为 $(10+5) \times (1+8) = 135$。

这些都是各场景下的最大值。因此，函数应返回 [112, 144, 143, 135]。

Sample grader

Sample grader 接收以下格式的输入：

• Line 1: $N \ M$
• Line $2 + i$ ($0 \le i \le N-1$): $A_1[i] \ B_1[i]$
• Line $2 + N + j$ ($0 \le j \le M-1$): $A_2[j] \ B_2[j]$
• Line $2 + N + M$: $Q$
• Line $3 + N + M + k$ ($0 \le k \le Q-1$): $L_1[k] \ R_1[k] \ L_2[k] \ R_2[k]$

Sample grader 输出以下内容：

• Line $1 + k$ ($0 \le k \le Q-1$): 函数 build_teams 返回数组的第 $k$ 个元素

请注意，Sample grader 可能与实际评测中使用的评测程序不同。