Nel giardino di Bessie ci sono $N$ piante, numerate da $1$ a $N$ ($2\leq N\leq 5\cdot 10^5$) da sinistra a destra. Bessie sa che la pianta $i$ richiede almeno $w_i$ ($0\leq w_i \leq 10^6$) unità d'acqua. Bessie ha un sistema di irrigazione molto particolare con $N-1$ canali, numerati da $1$ a $N-1$. A ogni canale $i$ è associato un costo unitario $c_i$ ($1\le c_i\le 10^6$), tale che Bessie può pagare $c_i k$ per fornire alle piante $i$ e $i+1$ ciascuna $k$ unità d'acqua, dove $k$ è un intero non negativo. Bessie è impegnata e potrebbe non avere il tempo di utilizzare tutti i canali. Per ogni $2\leq i \leq N$, calcola il costo minimo necessario per irrigare le piante da $1$ a $i$ usando soltanto i primi $i-1$ canali.

Input

La seconda riga contiene $N$ interi separati da spazi, $w_1, \ldots, w_N$. La terza riga contiene $N-1$ interi separati da spazi, $c_1, \ldots, c_{N-1}$.

La terza riga contiene $N-1$ interi separati da spazi, $c_1, \ldots, c_{N-1}$.

Output

Stampa $N-1$ interi su righe separate. L'intero in posizione $(i-1)$ deve essere il costo minimo per irrigare le prime $i$ piante usando i primi $i-1$ canali.

Esempi

Input 1

3
39 69 33
30 29

Output 1

2070
2127

Input 2

3
33 82 36
19 1

Output 2

1558
676

Input 3

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

Output 3

623
4099
4114
6269
6272
6827
8827

Vincoli

• Input 4: $N \leq 200$ e tutti i $w_i \leq 200$.
• Input 5-6: Tutti i $w_i \leq 200$.
• Input 7-10: $N \leq 5000$.
• Input 11-14: Tutti i $w_i$ e $c_i$ sono generati indipendentemente e uniformemente a caso.
• Input 15-19: Nessun vincolo aggiuntivo.