Mushroom Harvest

You are given two integer sequences of length n: a₁, a₂, ..., a_n and b₁, b₂, ..., b_n. Initially, on the morning of day 1 the i-th patch has b_i mushrooms. Every evening, on each patch the mushrooms grow by a_i (that is, a_i new mushrooms appear on patch i).

You are allowed to go out and harvest mushrooms once every morning. In one harvest you must choose a single patch and collect all the mushrooms there. Note that when you harvest a patch, its mushrooms are collected and the patch is reset; however, at the following evening its mushrooms will grow by its growth rate. You can visit the same patch on multiple days.

For k = 1, 2, ... , n, find the maximum total number of mushrooms you can collect if you plan an optimal schedule for the first k days. In other words, for each k output the maximum total mushrooms you can harvest from day 1 through day k if on each morning you choose one patch to harvest.

Note on dynamics: Suppose on day d the number of mushrooms on patch i is m. If you harvest patch i on that morning you collect m mushrooms and the patch resets. Then, in the evening, every patch (including the one you just harvested) has its mushroom count increased by its corresponding a_i. If you do not harvest from a patch, its mushrooms remain and the growth is added on top.

inputFormat

The input begins with a line containing one integer n (the number of patches/days).

The second line contains n space‐separated integers a₁, a₂, ..., a_n representing the daily growth for each patch.

The third line contains n space‐separated integers b₁, b₂, ..., b_n representing the initial number of mushrooms on each patch on the morning of day 1.

outputFormat

Output n integers. The k-th integer should be the maximum total number of mushrooms that can be collected during the first k days if you harvest optimally.

sample

3
1 2 3
3 2 1

3 7 14