Na Olimpíada Internacional de Informática de 20XX foi introduzida uma nova modalidade mista. Cada equipe consiste em um rapaz e uma moça resolvendo problemas juntos. Para formar a seleção, o comitê escolheu $N$ candidatos e $M$ candidatas. Os rapazes são numerados de $0$ a $N-1$ e as moças de $0$ a $M-1$.

A força de uma equipe depende das capacidades de conceber ideias e de implementação de ambos os membros. Cada capacidade é um inteiro entre $1$ e $10^9$, inclusive. O rapaz $i$ tem capacidades $A_1[i]$ e $B_1[i]$, respectivamente, e a moça $j$ tem $A_2[j]$ e $B_2[j]$. A força da equipe é definida como $(A_1[i]+A_2[j])\times(B_1[i]+B_2[j])$.

Todos foram selecionados após uma competição acirrada, portanto nenhum rapaz supera outro em ambas as capacidades. Mais precisamente, a capacidade de ideias cresce estritamente com o número e a implementação decresce estritamente: $A_1[i]<A_1[i+1]$ e $B_1[i]>B_1[i+1]$ para $0\le i\le N-2$. O mesmo vale para as moças: $A_2[j]<A_2[j+1]$ e $B_2[j]>B_2[j+1]$ para $0\le j\le M-2$.

O comitê quer maximizar a força da equipe em vários cenários. Há $Q$ cenários numerados de $0$ a $Q-1$. No cenário $k$, o número do rapaz deve estar em $[L_1[k],R_1[k]]$ e o da moça em $[L_2[k],R_2[k]]$, incluindo os extremos. Escreva um programa que encontre a maior força de uma equipe válida para cada cenário.

Detalhes de implementação

Implemente a função seguinte.

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$: Vetores de tamanho $N$. O rapaz $i$ tem capacidade de ideias $A_1[i]$ e de implementação $B_1[i]$ ($0\le i\le N-1$).
• $A_2,B_2$: Vetores de tamanho $M$. A moça $j$ tem capacidade de ideias $A_2[j]$ e de implementação $B_2[j]$ ($0\le j\le M-1$).
• $L_1,R_1,L_2,R_2$: Vetores de tamanho $Q$. No cenário $k$, o número do rapaz deve estar em $[L_1[k],R_1[k]]$ e o da moça em $[L_2[k],R_2[k]]$ ($0\le k\le Q-1$).
• Retorne um vetor $C$ de tamanho $Q$, em que $C[k]$ é a maior força de uma equipe no cenário $k$.

Nenhuma parte do código enviado pode executar funções de entrada ou saída.

Restrições

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

Subtarefas

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) Sem restrições adicionais.

Exemplos

1

Considere os valores seguintes:

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

O avaliador chama a função assim:

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])

No cenário $0$, o número do rapaz deve estar em $[0,4]$ e o da moça em $[1,3]$. Escolher o rapaz $1$ e a moça $3$ dá força $(7+9)\times(9+5)=224$. Essa é a maior força entre as equipes que satisfazem as condições.

No cenário $1$, o número do rapaz deve estar em $[2,3]$ e o da moça em $[0,2]$. Escolher o rapaz $2$ e a moça $2$ dá força $(8+5)\times(8+7)=195$. Essa é a maior força entre as equipes que satisfazem as condições.

No cenário $2$, o número do rapaz deve estar em $[1,1]$ e o da moça em $[0,0]$. Escolher o rapaz $1$ e a moça $0$ dá força $(7+1)\times(9+10)=152$.

Portanto, a função deve retornar $[224,195,152]$.

2

Considere os valores seguintes:

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

O avaliador chama a função assim:

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])

No cenário $0$, escolher o rapaz $0$ e a moça $1$ dá força $(1+6)\times(9+7)=112$.

No cenário $1$, escolher o rapaz $1$ e a moça $1$ dá força $(6+6)\times(5+7)=144$.

No cenário $2$, escolher o rapaz $2$ e a moça $0$ dá força $(8+5)\times(3+8)=143$.

No cenário $3$, escolher o rapaz $3$ e a moça $0$ dá força $(10+5)\times(1+8)=135$.

Todos esses valores são as maiores forças de equipes que satisfazem as condições dos respectivos cenários. Portanto, a função deve retornar $[112,144,143,135]$.

Avaliador de exemplo

O avaliador de exemplo lê a entrada no formato seguinte.

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

O avaliador de exemplo imprime o seguinte.

• Linha $1+k$ ($0\le k\le Q-1$): O elemento de índice $k$ do vetor retornado por build_teams.

O avaliador de exemplo pode ser diferente daquele usado na avaliação real.