O jardim de Bessie tem $N$ plantas numeradas de $1$ a $N$ ($2\leq N\leq 5\cdot 10^5$) da esquerda para a direita. Bessie sabe que a planta $i$ precisa de pelo menos $w_i$ ($0\leq w_i \leq 10^6$) unidades de água. Bessie tem um sistema de irrigação muito peculiar com $N-1$ canais, numerados de $1$ a $N-1$. Cada canal $i$ tem um custo unitário associado $c_i$ ($1\le c_i\le 10^6$), de modo que Bessie pode pagar $c_i k$ para fornecer às plantas $i$ e $i+1$, cada uma, $k$ unidades de água, onde $k$ é um inteiro não negativo. Bessie está ocupada e talvez não tenha tempo de usar todos os canais. Para cada $2\leq i \leq N$, calcule o custo mínimo necessário para regar as plantas de $1$ a $i$ usando apenas os primeiros $i-1$ canais.

Entrada

A segunda linha contém $N$ inteiros separados por espaços $w_1, \ldots, w_N$. A terceira linha contém $N-1$ inteiros separados por espaços $c_1, \ldots, c_{N-1}$.

A terceira linha contém $N-1$ inteiros separados por espaços $c_1, \ldots, c_{N-1}$.

Saída

Imprima $N-1$ inteiros, um por linha. O $(i-1)$-ésimo inteiro deve conter o custo mínimo para regar as primeiras $i$ plantas usando os primeiros $i-1$ canais.

Exemplos

Entrada 1

3
39 69 33
30 29

Saída 1

2070
2127

Entrada 2

3
33 82 36
19 1

Saída 2

1558
676

Entrada 3

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

Saída 3

623
4099
4114
6269
6272
6827
8827

Restrições

• Arquivo de entrada 4: $N \leq 200$, e todos os $w_i \leq 200$.
• Arquivos de entrada 5–6: todos os $w_i \leq 200$.
• Arquivos de entrada 7–10: $N \leq 5000$.
• Arquivos de entrada 11–14: todos os $w_i$ e $c_i$ são gerados de forma independente e uniformemente aleatória.
• Arquivos de entrada 15–19: nenhuma restrição adicional.