팀 만들기

20XX년 국제정보올림피아드에서는 혼성 종목이 신설되었다. 혼성 종목에서는 남학생 한 명과 여학생 한 명이 팀을 이루어 문제를 풀게 된다. 정보올림피아드위원회에서는 혼성 종목에 참가할 대표팀을 만들기 위해 $N$ 명의 남학생 후보와 $M$ 명의 여학생 후보를 선발했다. $N$ 명의 남학생 후보들에게는 $0$ 번부터 $N - 1$ 번까지의 번호가 붙어 있다. 마찬가지로, $M$ 명의 여학생 후보들에게는 $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$ 에 대해 $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]$ 이 성립한다.

정보올림피아드위원회에서는 다양한 시나리오에 따라 팀의 실력이 최대가 되도록 팀을 구성하고자 한다. $0$ 부터 $Q - 1$ 번까지 번호가 붙은 $Q$ 개의 시나리오가 존재한다. $k$ 번 시나리오에서, 남학생의 번호는 $L\_1\[k]$ 이상 $R\_1\[k]$ 이하가 되어야 하고, 여학생의 번호는 $L\_2\[k]$ 이상 $R\_2\[k]$ 이하가 되어야 한다. 각 시나리오에 대해, 조건을 만족하며 구성할 수 있는 팀의 실력의 최댓값을 구하는 프로그램을 작성하여라.

문제

제한