¡Bienvenidos al TV Time del Sr. Ant Tenna! En esta ronda del juego, se te dan $n$ cubos, donde el $i$-ésimo cubo tiene una capacidad máxima de $v_i$ volúmenes de agua. Al comienzo del juego, todos los cubos se llenarán completamente de agua, y tu misión es retener tanta agua como puedas durante los próximos $t$ segundos. Pero aquí está el giro: ¡estos cubos están rotos! El $i$-ésimo cubo tiene una velocidad de fuga de $l_i$, lo que significa que cada segundo después de que comienza el juego, el $i$-ésimo cubo pierde $l_i$ volúmenes de agua.
Antes de que comience el juego, puedes fusionar cualquier cantidad de cubos en uno solo. El cubo resultante tiene una capacidad igual a la capacidad máxima entre los cubos fusionados, y una velocidad de fuga igual a la velocidad de fuga mínima entre los cubos fusionados. Puedes realizar fusiones un número arbitrario de veces, pero deben llevarse a cabo antes de llenar cualquier cubo con agua.
Tenna plantea $q$ preguntas, donde la $i$-ésima pregunta tiene un límite de tiempo $t_i$. Para cada $1 \le i \le q$, calcula el volumen total máximo retenido después de $t_i$ segundos. Ten en cuenta que cada pregunta es independiente.
Entrada
Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 5 \times 10^4$) que indica el número de casos de prueba. Para cada caso de prueba:
La primera línea contiene un entero $n$ ($1 \le n \le 2 \times 10^5$), que indica el número de cubos.
La segunda línea contiene $n$ enteros $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), donde $v_i$ es la capacidad del $i$-ésimo cubo.
La tercera línea contiene $n$ enteros $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), donde $l_i$ es la velocidad de fuga del $i$-ésimo cubo.
La cuarta línea contiene un entero $q$ ($1 \le q \le 2 \times 10^5$), que indica el número de preguntas.
La quinta línea contiene $q$ enteros $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), donde $t_i$ es el límite de tiempo para la $i$-ésima consulta.
Se garantiza que ni la suma de $n$ ni la suma de $q$ de todos los casos de prueba superará $2 \times 10^5$.
Salida
Para cada caso de prueba, imprime una línea con $q$ enteros separados por un espacio, donde el $i$-ésimo entero es el volumen total máximo retenido después de $t_i$ segundos.
Ejemplos
2
4
5 4 7 6
2 1 3 2
3
3 1 2
4
19 47 21 13
5 14 2 3
5
5 2 6 1 4
4 14 8
43 67 38 77 48