Khu vườn của Bessie có $N$ cây được đánh số từ $1$ đến $N$ ($2\leq N\leq 5\cdot 10^5$) từ trái sang phải. Bessie biết rằng cây $i$ cần ít nhất $w_i$ ($0\leq w_i \leq 10^6$) đơn vị nước. Bessie có một hệ thống tưới tiêu rất đặc biệt với $N-1$ kênh, được đánh số từ $1$ đến $N-1$. Mỗi kênh $i$ có chi phí đơn vị tương ứng $c_i$ ($1\le c_i\le 10^6$), nghĩa là Bessie có thể trả $c_i k$ để cung cấp cho mỗi cây trong hai cây $i$ và $i+1$ một lượng $k$ đơn vị nước, trong đó $k$ là một số nguyên không âm. Bessie bận rộn và có thể không có thời gian sử dụng tất cả các kênh. Với mỗi $2\leq i \leq N$, hãy tính chi phí nhỏ nhất cần thiết để tưới các cây từ $1$ đến $i$ bằng cách chỉ sử dụng $i-1$ kênh đầu tiên.

Dữ liệu vào

Dòng thứ hai chứa $N$ số nguyên $w_1, \ldots, w_N$ cách nhau bởi dấu cách. Dòng thứ ba chứa $N-1$ số nguyên $c_1, \ldots, c_{N-1}$ cách nhau bởi dấu cách.

Dòng thứ ba chứa $N-1$ số nguyên $c_1, \ldots, c_{N-1}$ cách nhau bởi dấu cách.

Dữ liệu ra

In ra $N-1$ số nguyên, mỗi số trên một dòng. Số nguyên thứ $(i-1)$ phải là chi phí nhỏ nhất để tưới $i$ cây đầu tiên bằng $i-1$ kênh đầu tiên.

Ví dụ

Dữ liệu vào 1

3
39 69 33
30 29

Dữ liệu ra 1

2070
2127

Dữ liệu vào 2

3
33 82 36
19 1

Dữ liệu ra 2

1558
676

Dữ liệu vào 3

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

Dữ liệu ra 3

623
4099
4114
6269
6272
6827
8827

Giới hạn

• Bộ kiểm thử 4: $N \leq 200$, và mọi $w_i \leq 200$.
• Các bộ kiểm thử 5–6: Mọi $w_i \leq 200$.
• Các bộ kiểm thử 7–10: $N \leq 5000$.
• Các bộ kiểm thử 11–14: Mọi $w_i$ và $c_i$ được sinh độc lập, ngẫu nhiên với phân phối đều.
• Các bộ kiểm thử 15–19: Không có giới hạn bổ sung.