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.
/**
 * Created by Aminul on 3/10/2018.
 */

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class C_2 {
    public static void main(String[] args)throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt();
        int v[] = new int[n];
        for (int i = 0; i < n; i++) {
            v[i] = in.nextInt();
        }

        MyTreap treap = new MyTreap();
        for(int i = 0; i < n; i++){
            int t = in.nextInt();
            treap.insert(v[i]);
            pw.print(treap.solve(t)+" ");
        }


        pw.close();
    }

    static class MyTreap {
        static class Node {
            int key, lazy;
            long sum;
            double priority;
            Node left,right;
            int size;
            Node(int key) {
                this.key = key;
                this.sum = key;
                priority = Math.random();
                size = 1;
            }

            void update() {
                size = 1 + getSize(left) + getSize(right);
                sum =  getSum(left) + getSum(right) + key;
            }
            int getSize(Node root) {
                return root == null ? 0 : root.size;
            }
            long getSum(Node root) {return root == null ? 0 : root.sum;}
        }


        Node root;
        void insert(int k){
            root = insert(root, k);
        }
        void remove(int k){
            root = remove(root, k);
        }
        int getKth(int k){
            return kth(root, k);
        }
        int getSize(Node root) {
            return root == null ? 0 : root.size;
        }
        int size(){
            return getSize(root);
        }
        long getSum(Node root) {return root == null ? 0 : root.sum;}

        int orderOf(int k){ // number of elements < k
            return orderOf(root, k);
        }

        int orderOf(Node temp, int k){ // number of elements < k
            int x = 0;
            if(temp == null) return 0;
            if(temp.key < k) return getSize(temp.left) + 1 + orderOf(temp.right, k);
            else return orderOf(temp.left, k);
        }

        Node splitL, splitR;

        void splitRecursive(Node t, int x){
            if(t == null){
                splitL = null;
                splitR = null;
                return;
            }

            pushDown(t);

            if(t.key <= x){
                splitRecursive(t.right, x);
                t.right = splitL;
                splitL = t;
            }
            else{
                splitRecursive(t.left, x);
                t.left = splitR;
                splitR = t;
            }
            t.update();
        }

        void lazy_update(Node root, int x){
            if(root != null){
                root.key += x;
                root.lazy += x;
                root.sum += (long)root.size * x;
            }
        }

        long solve(int x){
            splitRecursive(root, x);
            long sum = getSum(splitL) + (long)getSize(splitR) * x;
            root = splitR;
            lazy_update(root, -x);
            return sum;
        }

        void pushDown(Node root){
            if(root == null || root.lazy == 0) return;
            if(root.left != null){
                root.left.key += root.lazy;
                root.left.lazy += root.lazy;
                root.left.sum += (long)root.lazy * root.left.size;
            }
            if(root.right != null){
                root.right.key += root.lazy;
                root.right.lazy += root.lazy;
                root.right.sum += (long)root.lazy * root.right.size;
            }
            root.lazy = 0;
        }


        Node merge(Node left, Node right) {
            pushDown(left); pushDown(right);
            if (left == null)
                return right;

            if (right == null)
                return left;
            if (left.priority > right.priority) {
                left.right = merge(left.right, right);
                left.update();
                return left;
            } else {
                right.left = merge(left, right.left);
                right.update();
                return right;
            }
        }

        Node insert(Node root, int x) {
            splitRecursive(root, x);
            return merge(merge(splitL, new Node(x)), splitR);
        }

        Node remove(Node root, int x) {
            if (root == null) {
                return null;
            }
            if (x < root.key) {
                root.left = remove(root.left, x);
                root.update();
                return root;
            } else if (x > root.key) {
                root.right = remove(root.right, x);
                root.update();
                return root;
            } else {
                return merge(root.left, root.right);
            }
        }

        int kth(Node root, int k) {
            if (k < getSize(root.left))
                return kth(root.left, k);
            else if (k > getSize(root.left))
                return kth(root.right, k - getSize(root.left) - 1);
            return root.key;
        }

        void print(Node root) {
            pushDown(root);
            if (root == null)
                return;
            print(root.left);
            System.out.print(root.key+","+root.sum+"; " );
            print(root.right);
        }

    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
        static final int ints[] = new int[128];

        public FastReader(InputStream is){
            for(int i='0';i<='9';i++) ints[i]=i-'0';
            this.is = is;
        }

        public int readByte(){
            if(lenbuf == -1)throw new InputMismatchException();
            if(ptrbuf >= lenbuf){
                ptrbuf = 0;
                try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
                if(lenbuf <= 0)return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        public int skip() {
            int b;
            while((b = readByte()) != -1 && isSpaceChar(b));
            return b;
        }

        public String next(){
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt(){
            int num = 0, b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
       /* public char nextChar() {
            return (char)skip();
        }*/

        public char[] next(int n){
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while(p < n && !(isSpaceChar(b))){
                buf[p++] = (char)b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        /*private char buff[] = new char[1005];
        public char[] nextCharArray(){
            int b = skip(), p = 0;
            while(!(isSpaceChar(b))){
                buff[p++] = (char)b;
                b = readByte();
            }
            return Arrays.copyOf(buff, p);
        }*/
    }
}