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

public class CFC948C{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        String s[];
        s = br.readLine().split(" ");
        long[] a = new long[n];
        long[] b = new long[n];
        long[] sum = new long[n];
        long[] total = new long[n];
        for(int i=0;i<n;i++){
            a[i] = Long.parseLong(s[i]);
        }
        s = br.readLine().split(" ");


        Node root = createTree(a, 0, n-1);


        for(int i=0;i<n;i++){
            b[i] = Long.parseLong(s[i]);
            if(i != 0){
                sum[i] = b[i] + sum[i-1];
            }else{
                sum[i] = b[i];
            }
        }
        int index = 0;
        for(int i=0;i<n;i++){
            long v = 0;
            if(i != 0) v = a[i]+sum[i-1];
            else v = a[i];
            index = search(sum, v);
            if(index < 0){
                total[i] += a[i]; 
                continue;
            }
            addCount(root, i, index);
            if(sum[index] != v){
                if(index + 1 < n){
                    total[index + 1] += v - sum[index];
                }
            }
        }

        for(int i=0;i<n;i++){
            int c = 0;
            c = getTotal(root, i);
            total[i] += b[i] * c;
        }

        for(int i=0;i<n;i++){
            sb.append(total[i] + " ");
        }
        System.out.println(sb);
    }
    private static Node createTree(long[] a, int l, int r){
        Node node = new Node();
        node.rl = l;
        node.rr = r;
        if(l == r){
            node.val = a[l];
            return node;
        }
        node.left = createTree(a, l, (l+r)/2);
        node.right = createTree(a, ((l+r)/2) + 1, r);
        node.val = -1;
        return node;
    }
    private static void addCount(Node root, int i, int index){
        if(root == null){
            return;
        }
        if(root.rl >= i && root.rr <= index){
            root.count++;
            return;
        }else if(root.rl > index || root.rr < i){
            return;
        }
        addCount(root.left, i, index);
        addCount(root.right, i, index);
    }
    private static int getTotal(Node root, int i){

        int total = 0;
        total = root.count;
        if(root.left != null){
            if(root.left.rl <= i && root.left.rr>=i){
                total += getTotal(root.left, i);
            }
        }
        if(root.right != null){
            if(root.right.rl <= i && root.right.rr>=i){
                total += getTotal(root.right, i);
            }
        }
        return total;
    }
    private static int search(long[] sum, long val){

        int l = 0;
        int h = sum.length - 1;
        if(sum[h] <=  val){
            return h;
        }
        if(sum[l] > val){
            return -1;
        }
        while(true){
            int mid = (l+h)/2;
            if(l == mid){
                return l;
            }
            if(sum[mid] == val){
                return mid;
            }
            if(sum[mid] > val){
                h = mid;
            }else{
                l = mid;
            }
        }
    }
}
class Node{
    long val = 0;
    Node left;
    Node right;
    int rl;
    int rr;
    int count = 0;
}
