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.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.StringTokenizer;

public class Main {
    
    static int n;
    static long[] v, t;
    
    public static void main(String[] args) throws UnsupportedEncodingException, IOException {
        Reader.init(System.in);
        StringBuilder out = new StringBuilder();
        n = Reader.nextInt();
        v = new long[n + 1];
        t = new long[n + 1];
        for(int i = 1; i <= n; i++)
            v[i] = Reader.nextLong();
        for(int i = 1; i <= n; i++)
            t[i] = t[i - 1] + Reader.nextLong();
        int[] cnt = new int[n + 1];
        long[] sm = new long[n + 1];
        for(int i = 1, best; i <= n; i++) {
            best = bs(i);
            if(best > -1) {
                sm[best] += v[i] - t[best - 1] + t[i - 1];
                cnt[best]++;
            }
        }
        for(int i = 1; i <= n; i++)
            out.append(sm[i] + (i - (cnt[i] += cnt[i - 1])) * (t[i] - t[i - 1])).append(' ');
        out.setCharAt(out.length() - 1, '\n');
        PrintWriter pw = new PrintWriter(System.out);
        pw.print(out);
        pw.close();
    }
    
    static int bs(int i) {
        int f = i, to = n, m, best = -1;
        while(f <= to) {
            m = (f + to) / 2;
            if(t[m] - t[i - 1] >= v[i]) {
                best = m;
                to = m - 1;
            } else
                f = m + 1;
        }
        return best;
    }
}

class Reader {

    static BufferedReader reader;
    static StringTokenizer tokenizer;

    static void init(InputStream input) throws UnsupportedEncodingException {
        reader = new BufferedReader(
                new InputStreamReader(input, "UTF-8"));
        tokenizer = new StringTokenizer("");
    }
    
    static void init(String url) throws FileNotFoundException {
        reader = new BufferedReader(new FileReader(url));
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static String nextLine() throws IOException {
        return reader.readLine();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
}