Yura adores the winter. Most of all he is delighted with the ice. But the winter is over and Yura will have to wait for the next one. In order not to be upset, the monkey gave Yura an ice machine. The device produces a certain amount of ice every day. At the beginning of the day number i the machine creates vi kilograms of ice and Yura puts this ice on the windowsill.

But not everything is so simple. Every day the ice on the windowsill melts. Namely, if the daytime temperature is x, then the weight of all existing pieces of ice decreases by x. If at some point the mass of ice piece is 0, then the piece disappears. Each piece melts independently of the other.

Note that the snowdrift, manufactured on the day i, also loses part of its mass on the same day.

You are given the initial masses of each piece of ice, as well as the temperature for each day. For each day, determine the total mass of melted ice.

Input

First line contains the number of days n (1 ≤ n ≤105). Second line contains n integers - the weight of the piece made at the day number i. Third line contains n integers - the temperature in the day i. All input data is non-negative. Any weight and temperature does not exceed 109.

Output

Print n numbers in one line, where i-th number is the total weight of the ice that melts at the i-th day.