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.*;
import java.util.*;
import java.math.*;
import java.lang.*;

import static java.lang.Math.*;

public class b implements Runnable {

    long mod = 1000000000 +7;
    InputReader read = new InputReader(System.in);
    /*
        less than return 1 => large number first;
    */

    public void run() {
        int n = read.nextInt();
        long[] nums = new long[n];
        long[] dec = new long[n];

        for(int i=0;i<n;i++){
            nums[i] = read.nextLong();
        }
        
        for(int i=0;i<n;i++){
            dec[i] = read.nextLong();
        }

        long pre = 0;
        long count = 0;

        PriorityQueue<Long> q =  new PriorityQueue();

        for(int i=0;i<n;i++){
            count = 0;
            long ans = 0;
            //System.out.println("dec: "+dec[i]+ " num: "+nums[i]);
            //System.out.println("pre: "+pre);
            if(dec[i] >= nums[i]){
                ans += Math.min(dec[i],nums[i]);

                while(q.size() > 0&&(pre + dec[i]) >= q.peek()){
                    ans += (q.poll()-pre);
                }

                ans += q.size()*dec[i];
            }else{
                ans += Math.min(dec[i],nums[i]);

                while(q.size() > 0&&(pre + dec[i]) >= q.peek()){
                    ans += (q.poll()-pre);
                }

                ans += q.size()*dec[i];
                q.add(nums[i]+pre);
            }
            pre += dec[i];
        System.out.print(ans+ " ");
        }
    }

    long log2(long a){ return (long)(Math.log(a)/Math.log(2));}

    public long modAdd(long a, long b) { return (a % mod + b % mod) % mod;}

    public long modSub(long a, long b) { return ((a % mod - b % mod) % mod);}

    public long modMul(long a, long b) { return ((a % mod) * (b % mod)) % mod;}

    public long modDiv(long a, long b) { return ((a % mod) * (binaryExp(b, mod - 2))) % mod;}

    public long modPow(long a) { return a % (mod - 1);}

    public long binaryExp(long a, long pow) {
        a = a % mod;
        if (pow == 0) {
            return 1;
        } else if (pow == 1) {
            return a;
        } else {
            long half = pow / 2;
            long temp = binaryExp(a, half);
            if (pow % 2 == 0) {
                return (temp * temp) % mod;
            } else {
                return ((a % mod) * ((temp * temp) % mod)) % mod;
            }
        }
    }

    public static void main(String args[]) throws Exception {
        new Thread(null, new b(), "Main", 1 << 27).start();
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));

            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

}