El jardín de Bessie tiene $N$ plantas numeradas del $1$ al $N$ ($2\leq N\leq 5\cdot 10^5$) de izquierda a derecha. Bessie sabe que la planta $i$ necesita al menos $w_i$ ($0\leq w_i \leq 10^6$) unidades de agua. Bessie tiene un sistema de riego muy peculiar con $N-1$ canales, numerados del $1$ al $N-1$. Cada canal $i$ tiene un coste unitario asociado $c_i$ ($1\le c_i\le 10^6$), de modo que Bessie puede pagar $c_i k$ para proporcionar $k$ unidades de agua a cada una de las plantas $i$ e $i+1$, donde $k$ es un entero no negativo. Bessie está ocupada y puede que no tenga tiempo para usar todos los canales. Para cada $2\leq i \leq N$, calcula el coste mínimo necesario para regar las plantas del $1$ al $i$ usando únicamente los primeros $i-1$ canales.

Entrada

La segunda línea contiene $N$ enteros separados por espacios, $w_1, \ldots, w_N$. La tercera línea contiene $N-1$ enteros separados por espacios, $c_1, \ldots, c_{N-1}$.

La tercera línea contiene $N-1$ enteros separados por espacios, $c_1, \ldots, c_{N-1}$.

Salida

Imprime $N-1$ enteros, uno por línea. El entero $(i-1)$-ésimo debe contener el coste mínimo para regar las primeras $i$ plantas usando los primeros $i-1$ canales.

Ejemplos

Entrada 1

3
39 69 33
30 29

Salida 1

2070
2127

Entrada 2

3
33 82 36
19 1

Salida 2

1558
676

Entrada 3

8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49

Salida 3

623
4099
4114
6269
6272
6827
8827

Restricciones

• Entrada 4: $N \leq 200$, y todos los $w_i \leq 200$.
• Entradas 5-6: Todos los $w_i \leq 200$.
• Entradas 7-10: $N \leq 5000$.
• Entradas 11-14: Todos los $w_i$ y $c_i$ se generan de forma independiente y uniformemente al azar.
• Entradas 15-19: Sin restricciones adicionales.