Bessie の庭には、左から右に $1$ から $N$ までの番号が付いた $N$ 本の植物があります ($2\leq N\leq 5\cdot 10^5$)。Bessie は、植物 $i$ に少なくとも $w_i$ ($0\leq w_i \leq 10^6$) 単位の水が必要だと知っています。Bessie は、$1$ から $N-1$ までの番号が付いた $N-1$ 本の水路からなる、とても風変わりな灌漑システムを持っています。各水路 $i$ には単位費用 $c_i$ ($1\le c_i\le 10^6$) が設定されており、Bessie は $c_i k$ を支払って植物 $i$ と $i+1$ のそれぞれに $k$ 単位の水を与えられます。ここで $k$ は非負整数です。Bessie は忙しく、すべての水路を使う時間がないかもしれません。各 $2\leq i \leq N$ について、最初の $i-1$ 本の水路だけを使って植物 $1$ から $i$ に水を与えるための最小費用を求めてください。

入力

2 行目には、空白で区切られた $N$ 個の整数 $w_1, \ldots, w_N$ が与えられます。3 行目には、空白で区切られた $N-1$ 個の整数 $c_1, \ldots, c_{N-1}$ が与えられます。

3 行目には、空白で区切られた $N-1$ 個の整数 $c_1, \ldots, c_{N-1}$ が与えられます。

出力

$N-1$ 個の整数を改行で区切って出力してください。$(i-1)$ 番目の整数は、最初の $i-1$ 本の水路を使って最初の $i$ 本の植物に水を与えるための最小費用です。

入出力例

入力 1

3
39 69 33
30 29

出力 1

2070
2127

入力 2

3
33 82 36
19 1

出力 2

1558
676

入力 3

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

出力 3

623
4099
4114
6269
6272
6827
8827

制約

• 入力 4：$N \leq 200$ であり、すべての $w_i \leq 200$。
• 入力 5–6：すべての $w_i \leq 200$。
• 入力 7–10：$N \leq 5000$。
• 入力 11–14：すべての $w_i$ と $c_i$ は、独立に一様ランダムに生成されます。
• 入力 15–19：追加の制約はありません。