팀 만들기

20XX년 국제정보올림피아드에 혼성 종목이 신설되었다. 혼성 종목에서는 남학생 한 명과 여학생 한 명이 팀을 이루어 문제를 푼다. 정보올림피아드위원회는 혼성 종목 대표팀을 만들기 위해 $N$명의 남학생 후보와 $M$명의 여학생 후보를 선발했다. 남학생 후보에게는 $0$번부터 $N - 1$번까지, 여학생 후보에게는 $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$인 모든 $i$에 대해 $A_1[i] < A_1[i + 1]$이고 $B_1[i] > B_1[i + 1]$이다. 여학생도 같은 규칙을 따른다. $0 \le j \le M - 2$인 모든 $j$에 대해 $A_2[j] < A_2[j + 1]$이고 $B_2[j] > B_2[j + 1]$이다.

위원회는 여러 시나리오마다 팀의 실력이 최대가 되도록 팀을 구성하려 한다. $0$번부터 $Q - 1$번까지 번호가 붙은 $Q$개의 시나리오가 있다. $k$번 시나리오에서 남학생 번호는 $L_1[k]$ 이상 $R_1[k]$ 이하여야 하고, 여학생 번호는 $L_2[k]$ 이상 $R_2[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$