Team Formation

In the 20XX International Informatics Olympiad, a mixed category was added. In this category, one boy and one girl form a team to solve problems. The olympiad committee selected $N$ boy candidates and $M$ girl candidates to form the national teams for the mixed category. The boy candidates are numbered from $0$ to $N - 1$, and the girl candidates are numbered from $0$ to $M - 1$.

A team's strength depends on both the ideation ability and the implementation ability of the two students on the team. Each ideation ability and implementation ability is an integer from $1$ to $10^9$. The ideation ability of boy $i$ is $A_1[i]$, and his implementation ability is $B_1[i]$. The ideation ability of girl $j$ is $A_2[j]$, and her implementation ability is $B_2[j]$. If boy $i$ and girl $j$ form a team, the strength of that team is $(A_1[i] + A_2[j]) \times (B_1[i] + B_2[j])$.

Every candidate was selected after fierce competition, so no boy is better than another boy in both ideation and implementation. More precisely, the ideation ability of the boys increases as the number grows, and the implementation ability decreases as the number grows. That is, $A_1[i] < A_1[i + 1]$ and $B_1[i] > B_1[i + 1]$ hold for every $0 \le i \le N - 2$. The girls follow the same rule: $A_2[j] < A_2[j + 1]$ and $B_2[j] > B_2[j + 1]$ hold for every $0 \le j \le M - 2$.

The committee wants to form a team with the maximum strength under several scenarios. There are $Q$ scenarios, numbered from $0$ to $Q - 1$. In scenario $k$, the boy's number must be at least $L_1[k]$ and at most $R_1[k]$, and the girl's number must be at least $L_2[k]$ and at most $R_2[k]$. Write a program that finds, for each scenario, the maximum strength of a team that can be formed under these conditions.

• $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]$ and $B_1[i] > B_1[i + 1]$
• For all $0 \le j \le M - 2$, $A_2[j] < A_2[j + 1]$ and $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$