In the 20XX International Olympiad in Informatics, a mixed-gender event was introduced. In this event, a team consists of one male student and one female student who work together to solve problems. To form the national team for this event, the Olympiad Committee selected $N$ male candidates and $M$ female candidates. The $N$ male candidates are numbered from $0$ to $N-1$. Similarly, the $M$ female candidates are numbered from $0$ to $M-1$.

The performance of a team is influenced by both the ideation ability and the implementation ability of the two students forming the team. The ideation and implementation abilities of students can be represented as integers between $1$ and $10^9$. The ideation ability of the $i$-th male student is $A_1[i]$, and their implementation ability is $B_1[i]$. Similarly, the ideation ability of the $j$-th female student is $A_2[j]$, and their implementation ability is $B_2[j]$. If the $i$-th male student and the $j$-th female student form a team, the team's performance is defined as $(A_1[i] + A_2[j]) \times (B_1[i] + B_2[j])$.

Since all students were selected through intense competition, no student is superior to another in both ideation and implementation ability. More precisely, the ideation ability of the male students increases as their index increases, while their implementation ability decreases as their index increases. That is, for $0 \le i \le N-2$, $A_1[i] < A_1[i+1]$ and $B_1[i] > B_1[i+1]$ hold. Similarly, for the female students, the ideation ability increases as the index increases, and the implementation ability decreases as the index increases. 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 Olympiad Committee wants to form teams to maximize the team's performance according to various scenarios. There are $Q$ scenarios, numbered from $0$ to $Q-1$. In the $k$-th scenario, the male student's index must be between $L_1[k]$ and $R_1[k]$ (inclusive), and the female student's index must be between $L_2[k]$ and $R_2[k]$ (inclusive). For each scenario, write a program that finds the maximum possible team performance satisfying the conditions.

Implementation Details

You must implement the following function:

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$: Arrays of length $N$. The $i$-th male student has ideation ability $A_1[i]$ and implementation ability $B_1[i]$. ($0 \le i \le N-1$)
• $A_2, B_2$: Arrays of length $M$. The $j$-th female student has ideation ability $A_2[j]$ and implementation ability $B_2[j]$. ($0 \le j \le M-1$)
• $L_1, R_1, L_2, R_2$: Arrays of length $Q$. In the $k$-th scenario, the male student's index must be between $L_1[k]$ and $R_1[k]$, and the female student's index must be between $L_2[k]$ and $R_2[k]$. ($0 \le k \le Q-1$)
• This function must return an array $C$ of size $Q$, where $C[k]$ is the maximum team performance possible for the $k$-th scenario.

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $1 \le N \le 100\,000$
• $1 \le M \le 100\,000$
• $1 \le A_1[i], B_1[i] \le 10^9$ for all $0 \le i \le N-1$
• $1 \le A_2[j], B_2[j] \le 10^9$ for all $0 \le j \le M-1$
• $A_1[i] < A_1[i+1]$ and $B_1[i] > B_1[i+1]$ for all $0 \le i \le N-2$
• $A_2[j] < A_2[j+1]$ and $B_2[j] > B_2[j+1]$ for all $0 \le j \le M-2$
• $1 \le Q \le 100\,000$
• $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$ for all $0 \le k \le Q-1$

Subtasks

1. (5 points) $N \le 500, M \le 500, Q \le 500$.
2. (10 points) $Q \le 20$.
3. (10 points) $L_2[k] = 0, R_2[k] = M-1$ for all $0 \le k \le Q-1$.
4. (35 points) $L_2[k] = R_2[k]$ for all $0 \le k \le Q-1$.
5. (40 points) No additional constraints.

Examples

Input 1

5 4
2 10
7 9
8 8
9 6
10 1
1 10
3 8
5 7
9 5
3
0 4 1 3
2 3 0 2
1 1 0 0

Output 1

224
195
152

Input 2

4 2
1 9
6 5
8 3
10 1
5 8
6 7
4
0 0 0 1
1 1 0 1
2 2 0 1
3 3 0 1

Output 2

112
144
143
135

Sample Grader

The sample grader receives input in the following format:

• 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]$

The sample grader outputs the following:

• Line $1 + k$ ($0 \le k \le Q-1$): The $k$-th element of the array returned by the function build_teams.

Note that the sample grader may differ from the grader used in actual grading.