En la Olimpiada Internacional de Informática de 20XX se introdujo una nueva prueba mixta. Cada equipo consta de un chico y una chica que resuelven problemas juntos. Para formar la selección, el comité eligió $N$ candidatos y $M$ candidatas. Los chicos se numeran de $0$ a $N-1$ y las chicas de $0$ a $M-1$.

La fuerza de un equipo depende de las capacidades de ideación e implementación de ambos miembros. Cada capacidad es un entero entre $1$ y $10^9$, inclusive. El chico $i$ tiene capacidades $A_1[i]$ y $B_1[i]$, respectivamente, y la chica $j$ tiene $A_2[j]$ y $B_2[j]$. La fuerza de su equipo se define como $(A_1[i]+A_2[j])\times(B_1[i]+B_2[j])$.

Todos fueron elegidos tras una dura competición, así que ningún chico supera a otro en ambas capacidades. Más precisamente, la ideación aumenta estrictamente con el número y la implementación disminuye estrictamente: $A_1[i]<A_1[i+1]$ y $B_1[i]>B_1[i+1]$ para $0\le i\le N-2$. Para las chicas ocurre lo mismo: $A_2[j]<A_2[j+1]$ y $B_2[j]>B_2[j+1]$ para $0\le j\le M-2$.

El comité quiere maximizar la fuerza del equipo en varios escenarios. Hay $Q$ escenarios numerados de $0$ a $Q-1$. En el escenario $k$, el número del chico debe estar en $[L_1[k],R_1[k]]$ y el de la chica en $[L_2[k],R_2[k]]$, con extremos incluidos. Escribe un programa que encuentre la fuerza máxima de un equipo válido en cada escenario.

Detalles de implementación

Implementa la siguiente función.

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$: Arreglos de longitud $N$. El chico $i$ tiene capacidad de ideación $A_1[i]$ y de implementación $B_1[i]$ ($0\le i\le N-1$).
• $A_2,B_2$: Arreglos de longitud $M$. La chica $j$ tiene capacidad de ideación $A_2[j]$ y de implementación $B_2[j]$ ($0\le j\le M-1$).
• $L_1,R_1,L_2,R_2$: Arreglos de longitud $Q$. En el escenario $k$, el número del chico debe estar en $[L_1[k],R_1[k]]$ y el de la chica en $[L_2[k],R_2[k]]$ ($0\le k\le Q-1$).
• Devuelve un arreglo $C$ de longitud $Q$, donde $C[k]$ es la máxima fuerza de un equipo en el escenario $k$.

Ninguna parte del código enviado puede ejecutar funciones de entrada o salida.

Restricciones

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

Subtareas

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) Sin restricciones adicionales.

Ejemplos

1

Considera los siguientes valores:

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

El evaluador llama a la función así:

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

En el escenario $0$, el número del chico debe estar en $[0,4]$ y el de la chica en $[1,3]$. Elegir al chico $1$ y a la chica $3$ da una fuerza de $(7+9)\times(9+5)=224$. Esta es la máxima fuerza entre los equipos que cumplen las condiciones.

En el escenario $1$, el número del chico debe estar en $[2,3]$ y el de la chica en $[0,2]$. Elegir al chico $2$ y a la chica $2$ da una fuerza de $(8+5)\times(8+7)=195$. Esta es la máxima fuerza entre los equipos que cumplen las condiciones.

En el escenario $2$, el número del chico debe estar en $[1,1]$ y el de la chica en $[0,0]$. Elegir al chico $1$ y a la chica $0$ da una fuerza de $(7+1)\times(9+10)=152$.

Por tanto, la función debe devolver $[224,195,152]$.

2

Considera los siguientes valores:

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

El evaluador llama a la función así:

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

En el escenario $0$, elegir al chico $0$ y a la chica $1$ da una fuerza de $(1+6)\times(9+7)=112$.

En el escenario $1$, elegir al chico $1$ y a la chica $1$ da una fuerza de $(6+6)\times(5+7)=144$.

En el escenario $2$, elegir al chico $2$ y a la chica $0$ da una fuerza de $(8+5)\times(3+8)=143$.

En el escenario $3$, elegir al chico $3$ y a la chica $0$ da una fuerza de $(10+5)\times(1+8)=135$.

Todos estos valores son las máximas fuerzas de equipos que cumplen las condiciones de sus respectivos escenarios. Por tanto, la función debe devolver $[112,144,143,135]$.

Evaluador de ejemplo

El evaluador de ejemplo lee la entrada con el siguiente formato.

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

El evaluador de ejemplo imprime lo siguiente.

• Línea $1+k$ ($0\le k\le Q-1$): El elemento de índice $k$ del arreglo devuelto por build_teams.

El evaluador de ejemplo puede diferir del usado en la evaluación real.