In Bessies Garten stehen $N$ Pflanzen, die von links nach rechts mit $1$ bis $N$ nummeriert sind ($2\leq N\leq 5\cdot 10^5$). Bessie weiß, dass Pflanze $i$ mindestens $w_i$ ($0\leq w_i \leq 10^6$) Einheiten Wasser benötigt. Bessie hat ein sehr ungewöhnliches Bewässerungssystem mit $N-1$ Kanälen, die von $1$ bis $N-1$ nummeriert sind. Jeder Kanal $i$ hat zugehörige Kosten pro Einheit $c_i$ ($1\le c_i\le 10^6$): Bessie kann $c_i k$ bezahlen, um die Pflanzen $i$ und $i+1$ jeweils mit $k$ Einheiten Wasser zu versorgen, wobei $k$ eine nicht negative ganze Zahl ist. Bessie ist beschäftigt und hat möglicherweise keine Zeit, alle Kanäle zu nutzen. Berechne für jedes $2\leq i \leq N$ die minimalen Kosten, um die Pflanzen $1$ bis $i$ zu bewässern, wenn nur die ersten $i-1$ Kanäle verwendet werden.

Eingabe

Die zweite Zeile enthält $N$ durch Leerzeichen getrennte ganze Zahlen $w_1, \ldots, w_N$. Die dritte Zeile enthält $N-1$ durch Leerzeichen getrennte ganze Zahlen $c_1, \ldots, c_{N-1}$.

Die dritte Zeile enthält $N-1$ durch Leerzeichen getrennte ganze Zahlen $c_1, \ldots, c_{N-1}$.

Ausgabe

Gib $N-1$ ganze Zahlen in jeweils einer eigenen Zeile aus. Die $(i-1)$-te ganze Zahl soll die minimalen Kosten enthalten, um die ersten $i$ Pflanzen mit den ersten $i-1$ Kanälen zu bewässern.

Beispiele

Eingabe 1

3
39 69 33
30 29

Ausgabe 1

2070
2127

Eingabe 2

3
33 82 36
19 1

Ausgabe 2

1558
676

Eingabe 3

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

Ausgabe 3

623
4099
4114
6269
6272
6827
8827

Beschränkungen

• Eingabe 4: $N \leq 200$, und alle $w_i \leq 200$.
• Eingaben 5–6: Alle $w_i \leq 200$.
• Eingaben 7–10: $N \leq 5000$.
• Eingaben 11–14: Alle $w_i$ und $c_i$ werden unabhängig und gleichverteilt zufällig erzeugt.
• Eingaben 15–19: Keine zusätzlichen Beschränkungen.