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.*;

public class C implements Runnable{
	public static void main (String[] args) {new Thread(null, new C(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");
		
		int n = fs.nextInt();
		int[] a = fs.nextIntArray(n);
		int[] b = fs.nextIntArray(n);
		long[] pref = new long[n];
		long[] res = new long[n];
		
		pref[n-1] = b[n-1];
		for(int i = n-2; i >= 0; i--) {
			pref[i] = pref[i+1] + b[i];
		}
		
		int[] mult = new int[n+1];
		res[n-1] = Math.min(b[n-1], a[n-1]);
		for(int i = n-2; i >= 0; i--) {
			res[i] += Math.min(a[i], b[i]);
			a[i] -= Math.min(a[i], b[i]);
			if(a[i] == 0) continue;
			int lo = i+1, hi = n-1;
			int dies = n;
			for(int bs = 0; bs < 50 && lo <= hi; bs++) {
				int mid = (lo + hi) / 2;
				long query = query(pref, i+1, mid);
				if(query >= a[i]) {
					//dead by now
					dies = mid;
					hi = mid-1;
				}
				else {
					lo = mid+1;
				}
			}
			
			if(dies-1 >= i+1) {
				mult[i+1]++;
				mult[dies]--;
			}
			if(dies < n)
				res[dies] += a[i] - query(pref, i+1, dies-1);
			
		}
		
		long sum = 0;
		for(int i = 0; i < n; i++) {
			sum += mult[i];
			res[i] += sum*b[i];
		}

		for(int i = 0; i < n; i++) out.print(res[i] + " ");

		out.close();
	}
	
	long query(long[] pre, int i, int j) {
		long res = pre[i];
		if(j + 1 < pre.length) res -= pre[j+1];
		return res;
	}

	void sort (int[] a) {
		int n = a.length;
		for(int i = 0; i < 50; i++) {
			Random r = new Random();
			int x = r.nextInt(n), y = r.nextInt(n);
			int temp = a[x];
			a[x] = a[y];
			a[y] = temp;
		}
		Arrays.sort(a);
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				//                br = new BufferedReader(new FileReader("testdata.out"));
				st = new StringTokenizer("");
			} catch (Exception e){e.printStackTrace();}
		}
		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
		public int nextInt() {return Integer.parseInt(next());}
		public long nextLong() {return Long.parseLong(next());}
		public double nextDouble() {return Double.parseDouble(next());}

		public String nextLine() {
			String line = "";
			try {line = br.readLine();}
			catch (Exception e) {e.printStackTrace();}
			return line;
		}
		public Integer[] nextIntegerArray(int n) {
			Integer[] a = new Integer[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public char[] nextCharArray() {return nextLine().toCharArray();}
	}

}