Team Building

This problem is adapted from the 2023 International Olympiad in Informatics representative student selection contest. In the 20XX IOI, a new mixed-team event is introduced where each team consists of one boy and one girl. The committee has selected N boy candidates and M girl candidates. The boys are numbered from 0 to N-1 and the girls from 0 to M-1.

Each candidate has two attributes: thinking ability and programming ability, each represented by an integer between 1 and 10⁹. For boys, the i-th candidate has thinking ability A₁[i] and programming ability B₁[i]. For girls, the j-th candidate has thinking ability A₂[j] and programming ability B₂[j]. If boy i and girl j form a team, the team strength is defined as:

$$ (A_1[i] + A_2[j]) \times (B_1[i] + B_2[j]) $$

Notably, the candidates are sorted by a natural dominance property: for boys the thinking ability increases and programming ability decreases with the index, i.e., for every i with 0 ≤ i ≤ N − 2 we have

$$ A_1[i] B_1[i+1]. $$

A similar property holds for the girls: for 0 ≤ j ≤ M − 2,

$$ A_2[j] B_2[j+1]. $$

There are Q scenarios. In the k-th scenario, you are only allowed to choose boys with indices in the range [L1[k], R1[k]] and girls with indices in the range [L2[k], R2[k]]. Your task is to determine the maximum team strength that can be achieved in each scenario.

You need to implement the following function:

vector 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);

Note that the solution code should not contain any input/output operations.

Hint: Thanks to the ordering of the candidates, the optimal team in any scenario can be obtained by considering only the boundary candidates of the provided ranges.

inputFormat

The input is provided via function arguments without direct I/O. However, if one were to simulate the input, the format is as follows:

• The first line contains three integers: N, M, Q.
• The second line contains N integers representing the array A1.
• The third line contains N integers representing the array B1.
• The fourth line contains M integers representing the array A2.
• The fifth line contains M integers representing the array B2.
• The next Q lines each contain four integers: L1[k], R1[k], L2[k], R2[k].

All arrays satisfy the property that the thinking ability increases and the programming ability decreases as the index increases.

outputFormat

The output is a list (or vector) of Q integers where the k-th integer is the maximum team strength that can be achieved in the k-th scenario.

The team strength for a pair (i, j) is given in latex format as: $$ (A_1[i] + A_2[j]) \times (B_1[i] + B_2[j]) $$. Ensure that your program computes this value precisely for each valid pair in the scenario.

sample

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

50