W ogrodzie Bessie rośnie $N$ roślin, ponumerowanych od $1$ do $N$ ($2\leq N\leq 5\cdot 10^5$) od lewej do prawej. Bessie wie, że roślina $i$ potrzebuje co najmniej $w_i$ ($0\leq w_i \leq 10^6$) jednostek wody. Bessie ma bardzo osobliwy system nawadniania z $N-1$ kanałami, ponumerowanymi od $1$ do $N-1$. Każdy kanał $i$ ma przypisany koszt jednostkowy $c_i$ ($1\le c_i\le 10^6$): Bessie może zapłacić $c_i k$, aby dostarczyć roślinom $i$ oraz $i+1$ po $k$ jednostek wody, gdzie $k$ jest nieujemną liczbą całkowitą. Bessie jest zajęta i może nie mieć czasu na użycie wszystkich kanałów. Dla każdego $2\leq i \leq N$ oblicz minimalny koszt podlania roślin od $1$ do $i$, używając wyłącznie pierwszych $i-1$ kanałów.

Wejście

Drugi wiersz zawiera $N$ liczb całkowitych $w_1, \ldots, w_N$, oddzielonych spacjami. Trzeci wiersz zawiera $N-1$ liczb całkowitych $c_1, \ldots, c_{N-1}$, oddzielonych spacjami.

Trzeci wiersz zawiera $N-1$ liczb całkowitych $c_1, \ldots, c_{N-1}$, oddzielonych spacjami.

Wyjście

Wypisz $N-1$ liczb całkowitych, każdą w osobnym wierszu. Liczba na pozycji $(i-1)$ powinna być minimalnym kosztem podlania pierwszych $i$ roślin za pomocą pierwszych $i-1$ kanałów.

Przykład

Wejście 1

3
39 69 33
30 29

Wyjście 1

2070
2127

Wejście 2

3
33 82 36
19 1

Wyjście 2

1558
676

Wejście 3

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

Wyjście 3

623
4099
4114
6269
6272
6827
8827

Ograniczenia

• Dane wejściowe 4: $N \leq 200$ oraz wszystkie $w_i \leq 200$.
• Dane wejściowe 5–6: Wszystkie $w_i \leq 200$.
• Dane wejściowe 7–10: $N \leq 5000$.
• Dane wejściowe 11–14: Wszystkie $w_i$ i $c_i$ są losowane niezależnie z rozkładu jednostajnego.
• Dane wejściowe 15–19: Brak dodatkowych ograniczeń.