Irrigation Optimization

Bessie has a garden with N plants numbered from 1 to N (2 ≤ N ≤ 5·10⁵). Each plant i requires at least \(w_i\) units of water (0 ≤ w_i ≤ 10⁶). Bessie’s irrigation system is unusual – it has N-1 canals (numbered 1 to N-1). Canal i can be used to deliver water simultaneously to plants i and i+1: by paying a cost of c_i * k (1 ≤ c_i ≤ 10⁶) you can provide k units of water to both plants (where k is any nonnegative integer).

Bessie is very busy, so she may choose not to use all the canals. For every 2 ≤ i ≤ N she wonders: if only the first i-1 canals are available, what is the minimum cost to water plants 1 through i (so that each plant’s water requirement is met)? In other words, if we choose nonnegative integers x₁, x₂, …, x_i-1 representing how many water‐units are delivered by canals 1 through i-1, then the solution must satisfy:

• Plant 1: x₁ ≥ w₁.
• For 2 ≤ j ≤ i-1: x_j-1 + x_j ≥ w_j.
• Plant i: x_i-1 ≥ w_i.

The objective is to minimize the total cost

[ \text{Cost} = \sum_{j=1}^{i-1} c_j \cdot x_j. ]

Note: In an optimal solution the constraints will be met exactly when possible. However, because the same canal’s water can help two neighboring plants, there is freedom to “shift” water between canals. One may think of choosing how much water canal 1 provides (x₁) as a free variable; then for every 2 ≤ j ≤ i-1, the minimal requirement is x_j = max(w_j - x_j-1, 0) except that later a canal might be forced to deliver extra water to cover a later plant’s need. (It can be shown that there is an optimal solution in which no canal delivers extra water beyond what is necessary.)

Your task is to compute, for each i from 2 to N, the minimum cost required to water plants 1 through i using only canals 1 through i-1.

inputFormat

The input begins with a line containing a single integer N (2 ≤ N ≤ 5·10⁵). The second line contains N space‐separated integers w₁, w₂, …, w_N (0 ≤ w_i ≤ 10⁶) representing the water requirements of the plants. The third line contains N-1 space‐separated integers c₁, c₂, …, c_N-1 (1 ≤ c_i ≤ 10⁶) representing the per‐unit cost for each canal.

outputFormat

Output a single line with N-1 space‐separated integers. The i^th integer (for 2 ≤ i ≤ N) should be the minimum cost to water plants 1 through i using only canals 1 through i-1.

sample

3
3 1 3
5 1

15 18