Ash like soup very much! So, on the Raksha Bandhan day, his sister gave him a soup maker as a gift. Soup maker in the ith hour will make volume Vi liters of soup and pours it in a bowl.
Each hour, the Volume of soup in every bowl is reduced due to evaporation. More precisely, when the temperature on a given hour is Ti, the Volume of soup in every bowl will reduce its volume by Ti. If this would reduce the volume of soup to or below zero, Bowl gets empty. All bowls are independent of each other.
Note that the Volume of soup in every bowl made in an hour i already lose part of its volume at the same hour. In an extreme case, this may mean that there is no soup left in the bowl at the end of a particular hour.
You are given the initial volumes of soup in bowls and the temperature on each hour. Determine the total volume of soup evaporated in each hour.
Input
The first line contains a single integer N (1 ≤ N ≤ 10^5) — the number of hours.
The second line contains N integers V 1, V 2, …, V N (0 ≤ V i ≤ 10^9), where V i is the initial volume of soup made in an hour i.
The third line contains N integers T 1, T 2, …, T N (0 ≤ T i ≤ 10^9), where T i is the temperature in an hour i.
Output
Output a single line with N integers, where the i-th integer represents the total volume of soup melted in an hour i.
Examples
Input
3
10 10 5
5 7 2
Output
5 12 4
Input
5
30 25 20 15 10
9 10 12 4 13
Output
9 20 35 11 25
Note
In the first sample, In the first hour, 10 liters of soup is prepared, which evaporates to the size of 5 at the same hour. In the second hour, another 10 liters of soup is made. Since it is a bit warmer than the hour before, the first bowl gets empty while the second bowl shrinks to 3. At the end of the second hour, only one bowl with 3 liters soup is left. In the third hour, another bowl with less volume of soup is made, but as the temperature dropped too, both bowls survive till the end of the hour.

见题面

见题面