20XX 年の国際情報オリンピックに混合種目が新設されました。この種目では男子 1 人と女子 1 人がチームで問題を解きます。委員会は代表チームを作るため、男子候補 $N$ 人と女子候補 $M$ 人を選びました。男子の番号は $0$ から $N-1$、女子の番号は $0$ から $M-1$ です。

チームの実力には 2 人の発想力と実装力の両方が影響します。各能力は $1$ 以上 $10^9$ 以下の整数です。男子 $i$ の発想力は $A_1[i]$、実装力は $B_1[i]$、女子 $j$ のそれぞれの能力は $A_2[j]$ と $B_2[j]$ です。この 2 人のチームの実力は $(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]$ です。

委員会は様々なシナリオで実力が最大になるチームを作りたいと考えています。シナリオは $Q$ 個あり、番号は $0$ から $Q-1$ です。シナリオ $k$ では男子の番号は $L_1[k]$ 以上 $R_1[k]$ 以下、女子の番号は $L_2[k]$ 以上 $R_2[k]$ 以下でなければなりません。各シナリオの条件を満たすチームの最大実力を求めるプログラムを書いてください。

実装の詳細

次の関数を実装してください。

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$：長さ $N$ の配列。男子 $i$ の発想力は $A_1[i]$、実装力は $B_1[i]$ です（$0\le i\le N-1$）。
• $A_2,B_2$：長さ $M$ の配列。女子 $j$ の発想力は $A_2[j]$、実装力は $B_2[j]$ です（$0\le j\le M-1$）。
• $L_1,R_1,L_2,R_2$：長さ $Q$ の配列。シナリオ $k$ で男子の番号は $[L_1[k],R_1[k]]$、女子の番号は $[L_2[k],R_2[k]]$ に属さなければなりません（$0\le k\le Q-1$）。
• 長さ $Q$ の配列 $C$ を返してください。$C[k]$ はシナリオ $k$ で作れるチームの実力の最大値です。

提出するソースコードのどの部分でも入出力関数を実行してはいけません。

制約

• $1\le N\le100\,000$
• $1\le M\le100\,000$
• $\forall i\in[0,N-1]:\quad1\le A_1[i],B_1[i]\le10^9$
• $\forall j\in[0,M-1]:\quad1\le A_2[j],B_2[j]\le10^9$
• $\forall i\in[0,N-2]:\quad A_1[i]<A_1[i+1],\ B_1[i]>B_1[i+1]$
• $\forall j\in[0,M-2]:\quad A_2[j]<A_2[j+1],\ B_2[j]>B_2[j+1]$
• $1\le Q\le100\,000$
• $\forall k\in[0,Q-1]:\quad0\le L_1[k]\le R_1[k]\le N-1$
• $\forall k\in[0,Q-1]:\quad0\le L_2[k]\le R_2[k]\le M-1$

小課題

1. (5) $N\le500,\ M\le500,\ Q\le500$
2. (10) $Q\le20$
3. (10) $\forall k\in[0,Q-1]:\quad L_2[k]=0,\ R_2[k]=M-1$
4. (35) $\forall k\in[0,Q-1]:\quad L_2[k]=R_2[k]$
5. (40) 追加の制約なし。

入出力例

1

次の値の場合を考えます。

$N=5$, $M=4$, $A_1=[2,7,8,9,10]$, $B_1=[10,9,8,6,1]$, $A_2=[1,3,5,9]$, $B_2=[10,8,7,5]$, $Q=3$, $L_1=[0,2,1]$, $R_1=[4,3,1]$, $L_2=[1,0,0]$, $R_2=[3,2,0]$.

グレーダは次のように関数を呼び出します。

build_teams([2, 7, 8, 9, 10], [10, 9, 8, 6, 1], [1, 3, 5, 9], [10, 8, 7, 5],
[0, 2, 1], [4, 3, 1], [1, 0, 0], [3, 2, 0])

シナリオ $0$ では、男子の番号は $[0,4]$、女子の番号は $[1,3]$ に属する必要があります。男子 $1$ と女子 $3$ を選ぶと実力は $(7+9)\times(9+5)=224$ です。 これは条件を満たすチームの最大実力です。

シナリオ $1$ では、男子の番号は $[2,3]$、女子の番号は $[0,2]$ に属する必要があります。男子 $2$ と女子 $2$ を選ぶと実力は $(8+5)\times(8+7)=195$ です。 これは条件を満たすチームの最大実力です。

シナリオ $2$ では、男子の番号は $[1,1]$、女子の番号は $[0,0]$ に属する必要があります。男子 $1$ と女子 $0$ を選ぶと実力は $(7+1)\times(9+10)=152$ です。

したがって、関数は $[224,195,152]$ を返す必要があります。

2

次の値の場合を考えます。

$N=4$, $M=2$, $A_1=[1,6,8,10]$, $B_1=[9,5,3,1]$, $A_2=[5,6]$, $B_2=[8,7]$, $Q=4$, $L_1=[0,1,2,3]$, $R_1=[0,1,2,3]$, $L_2=[0,0,0,0]$, $R_2=[1,1,1,1]$.

グレーダは次のように関数を呼び出します。

build_teams([1, 6, 8, 10], [9, 5, 3, 1], [5, 6], [8, 7], [0, 1, 2, 3], [0, 1,
2, 3], [0, 0, 0, 0], [1, 1, 1, 1])

シナリオ $0$ で男子 $0$ と女子 $1$ を選ぶと実力は $(1+6)\times(9+7)=112$ です。

シナリオ $1$ で男子 $1$ と女子 $1$ を選ぶと実力は $(6+6)\times(5+7)=144$ です。

シナリオ $2$ で男子 $2$ と女子 $0$ を選ぶと実力は $(8+5)\times(3+8)=143$ です。

シナリオ $3$ で男子 $3$ と女子 $0$ を選ぶと実力は $(10+5)\times(1+8)=135$ です。

これらはすべて各シナリオの条件を満たすチームの実力の最大値です。 したがって、関数は $[112,144,143,135]$ を返す必要があります。

サンプルグレーダ

サンプルグレーダは次の形式で入力を受け取ります。

• $1$ 行: $N\ M$
• $2+i$ ($0\le i\le N-1$) 行: $A_1[i]\ B_1[i]$
• $2+N+j$ ($0\le j\le M-1$) 行: $A_2[j]\ B_2[j]$
• $2+N+M$ 行: $Q$
• $3+N+M+k$ ($0\le k\le Q-1$) 行: $L_1[k]\ R_1[k]\ L_2[k]\ R_2[k]$

サンプルグレーダは次を出力します。

• $1+k$ ($0\le k\le Q-1$) 行: build_teams が返す配列の添字 $k$ の要素。

サンプルグレーダは実際の採点に使うグレーダと異なる場合があります。