https://www.acmicpc.net/problem/27608

# KOITST 23 Team Building

In the International Olympiad in Informatics (IOI) of the year 20XX, a mixed-gender event has been introduced. In this mixed event, one male student and one female student form a team to solve problems. The IOI committee selected representative teams for the mixed event by choosing $N$ male student candidates and $M$ female student candidates. The male student candidates are numbered from $0$ to $N - 1$, and similarly, the female student candidates are numbered from $0$ to $M - 1$.

The team's performance is influenced by the creative and implementation abilities of the two students. The creative and implementation abilities of the students can be represented by integers ranging from $1$ to $10^9$. The creative ability of the $i$-th male student is denoted as $A_1[i]$, and the implementation ability is denoted as $B_1[i]$. Similarly, the creative ability of the $j$-th female student is $A_2[j]$, and the implementation ability is $B_2[j]$. If the $i$-th male student and the $j$-th female student form a team, their performance is defined as $(A_{1}[i] + A_{2}[j]) \times (B_{1}[i] + B_{2}[j])$.

Since the students are selected as candidates after intense competition, no male student has both creative and implementation abilities superior to another male student. Specifically, for $0 \le i \le N - 2$, it holds that $A_1[i] < A_1[i + 1]$ and $B_1[i] > B_1[i + 1]$. Similarly, for female students, the creative ability increases and the implementation ability decreases with the student number. That is, for $0 \le j \le M - 2$, $A_2[j] < A_2[j + 1]$ and $B_2[j] > B_2[j + 1]$ hold.

The IOI committee aims to compose teams to maximize the team's performance under various scenarios. There are $Q$ scenarios numbered from $0$ to $Q - 1$. In the $k$-th scenario, the male student's number should be between $L_1[k]$ and $R_1[k]$, and the female student's number should be between $L_2[k]$ and $R_2[k]$. For each scenario, you need to write a program to find the maximum value of the team's performance that can be composed while satisfying the given conditions.

# Implementation

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)

Implement this function

# Constraints

* $1 \le N \le 100,000$
* $1 \le M \le 100,000$
* For all $0 \le i \le N - 1$, $1 \le A_1[i], B_1[i] \le 10^9$
* For all $0 \le j \le M - 1$, $1 \le A_2[j], B_2[j] \le 10^9$
* For all $0 \le i \le N - 2$, $A_1[i] < A_1[i + 1]$, $B_1[i] > B_1[i + 1]$
* For all $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$
* For all $0 \le k \le Q - 1$, $0 \le L_1[k] \le R_1[k] \le N - 1$
* For all $0 \le k \le Q - 1$, $0 \le L_2[k] \le R_2[k] \le M - 1$

# Subtask

# Examples

## Example 1

$N = 5$, $M = 4$, $A_1 = [2, 7, 8, 9, 10]$, $B_1 = [10, 9, 8, 6, 1]$, $A_2 = [1, 3, 5, 9]$, $B_2 = [10, 8, 7, 5]$, $Q = 3$, $L_1 = [0, 2, 1]$, $R_1 = [4, 3, 1]$, $L_2 = [1, 0, 0]$, $R_2 = [3, 2, 0]$.

Consider the following scenarios:

The grader calls the function as follows:

`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]).`

In scenario 0, the male student's number should be between 0 and 4, and the female student's number should be between 1 and 3. Teaming up the 1st male student with the 3rd female student results in a team ability of $(7 + 9) \times (9 + 5) = 224$, which is the maximum team ability satisfying the conditions.

In scenario 1, the male student's number should be between 2 and 3, and the female student's number should be between 0 and 2. Teaming up the 2nd male student with the 2nd female student results in a team ability of $(8 + 5) \times (8 + 7) = 195$, which is the maximum team ability satisfying the conditions.

In scenario 2, the male student's number should be 1, and the female student's number should be 0. Teaming up the 1st male student with the 1st female student results in a team ability of $(7 + 1) \times (9 + 10) = 152$.

Therefore, the function should return $[224, 195, 152]$.

## Example 2

$N = 4$, $M = 2$, $A_1 = [1, 6, 8, 10]$, $B_1 = [9, 5, 3, 1]$, $A_2 = [5, 6]$, $B_2 = [8, 7]$, $Q = 4$, $L_1 = [0, 1, 2, 3]$, $R_1 = [0, 1, 2, 3]$, $L_2 = [0, 0, 0, 0]$, $R_2 = [1, 1, 1, 1]$.

Consider the following scenarios:

The grader calls the function as follows:

`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]).`

In scenario 0, selecting the 0th male student and the 1st female student results in a team ability of $(1 + 6) \times (9 + 7) = 112$.

In scenario 1, selecting the 1st male student and the 1st female student results in a team ability of $(6 + 6) \times (5 + 7) = 144$.

In scenario 2, selecting the 2nd male student and the 0th female student results in a team ability of $(8 + 5) \times (3 + 8) = 143$.

In scenario 3, selecting the 3rd male student and the 0th female student results in a team ability of $(10 + 5) \times (1 + 8) =