Alice likes snow a lot! Unfortunately, this year's winter is already over, and she can't expect to have any more of it. Bob has thus bought her a gift — a large snow maker. He plans to make some amount of snow every day. On day i he will make a pile of snow of volume Vi and put it in her garden.

Each day, every pile will shrink a little due to melting. More precisely, when the temperature on a given day is Ti, each pile will reduce its volume by Ti. If this would reduce the volume of a pile to or below zero, it disappears forever. All snow piles are independent of each other. 

Note that the pile made on day i already loses part of its volume on the same day. In an extreme case, this may mean that there are no piles left at the end of a particular day.

You are given the initial pile sizes and the temperature on each day. Determine the total volume of snow melted on each day. 

Input

The first line contains a single integer N (1 ≤ N ≤ 105) — the number of days. 

The second line contains N integers V1, V2, ..., VN (0 ≤ Vi ≤ 109), where Vi is the initial size of a snow pile made on the day i.

The third line contains N integers T1, T2, ..., TN (0 ≤ Ti ≤ 109), where Ti is the temperature on the day i.

Output

Output a single line with N integers, where the i-th integer represents the total volume of snow melted on day 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, Bob first makes a snow pile of volume 10, which melts to the size of 5 on the same day. On the second day, he makes another pile of size 10. Since it is a bit warmer than the day before, the first pile disappears completely while the second pile shrinks to 3. At the end of the second day, he has only a single pile of size 3. On the third day he makes a smaller pile than usual, but as the temperature dropped too, both piles survive till the end of the day.
#include <bits/stdc++.h>
using namespace std;
long long n, m;
long long ans[400005], s[400005], f[400005], tag[400005], v[400005], t[400005],
    ps[400005];
long long ask(long long x) {
  long long l = 1, r = n, mid, pos = 0;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (s[mid] == x) return mid;
    if (s[mid] < x)
      pos = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return pos;
}
void change(long long x, long long l, long long r, long long st, long long en,
            long long y) {
  if (l == st && r == en) {
    f[x] += y, tag[x] += y;
    return;
  }
  long long mid = (l + r) >> 1, s = x << 1;
  f[s] += tag[x], f[s + 1] += tag[x], tag[s] += tag[x], tag[s + 1] += tag[x],
      tag[x] = 0;
  if (en <= mid)
    change(s, l, mid, st, en, y);
  else if (st > mid)
    change(s + 1, mid + 1, r, st, en, y);
  else
    change(s, l, mid, st, mid, y), change(s + 1, mid + 1, r, mid + 1, en, y);
  f[x] = f[s] + f[s + 1];
}
long long find(long long x, long long l, long long r, long long ps) {
  if (l == r) return f[x];
  long long mid = (l + r) >> 1, s = x << 1;
  f[s] += tag[x], f[s + 1] += tag[x], tag[s] += tag[x], tag[s + 1] += tag[x],
      tag[x] = 0;
  if (ps <= mid)
    find(s, l, mid, ps);
  else
    find(s + 1, mid + 1, r, ps);
}
int main() {
  scanf("%I64d", &n);
  for (int i = 1; i <= n; i++) scanf("%I64d", &v[i]);
  for (int i = 1; i <= n; i++) scanf("%I64d", &t[i]), s[i] = s[i - 1] + t[i];
  for (int i = 1; i <= n; i++) {
    long long k = v[i] + s[i - 1], o;
    ps[i] = ask(k);
    o = v[i] - (s[ps[i]] - s[i - 1]);
    ans[ps[i] + 1] += o;
  }
  for (int i = 1; i <= n; i++) {
    if (i > ps[i]) continue;
    change(1, 1, n, i, ps[i], 1);
  }
  for (int i = 1; i <= n; i++)
    ans[i] += (long long)find(1, 1, n, i) * (long long)t[i];
  for (int i = 1; i <= n; i++) printf("%I64d ", ans[i]);
  return 0;
}
