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 V_{i} 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 T_{i}, each pile will reduce its volume by T_{i}. 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 ≤ 10^5) — the number of days. 

The second line contains N integers V_1, V_2, ..., V_{N} (0 ≤ V_{i} ≤ 10^9), where V_{i} is the initial size of a snow pile made on the day i.

The third line contains N integers T_1, T_2, ..., T_{N} (0 ≤ T_{i} ≤ 10^9), where T_{i} 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.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
vs = [int(x) for x in input().split()]
ts = [int(x) for x in input().split()]

sumt = 0
for i, t in enumerate(ts):
    vs[i]+=sumt
    sumt+=t

vs.sort()

tl, tr = 0, 0
il, ir = 0, 0
for ind, t in enumerate(ts): #check
    tl = tr
    tr += t
    while ir < n and vs[ir] <= tr: ir += 1
    cur_sum = 0
    while il < ir:
        cur_sum += vs[il]-tl
        il+=1
##    print(ir, tl, tr,  cur_sum)
    cur_sum += t * ((n-ir) - (n-ind-1))
    print(cur_sum, end=" ")
    


from itertools import accumulate
import bisect

n = int(input())
v = list(map(int, input().split()))
t = list(map(int, input().split()))

ns = [0] * n
lo = [0] * n

tt = list(accumulate(t))
#print(tt)
for i in range(n):
    dd = v[i]
    a = 0
    if i != 0:
        dd += tt[i - 1]
        a = tt[i - 1]
    ns[i] += 1
    k = bisect.bisect_right(tt, dd)
    #print(dd,k)
    if k < n:
        ns[k] -= 1

        lo[k] +=  + v[i] + a
        if k != 0:
            lo[k] -= tt[k - 1]
#print(lo)
ns = list(accumulate(ns))
#print(ns)
for i in range(n):
    lo[i] += t[i] * ns[i]

print(' '.join(list(map(str, lo))))


# -*- coding: utf - 8 -*-
"""""""""""""""""""""""""""""""""""""""""""""
|    author: mr.math - Hakimov Rahimjon     |
|    e-mail: mr.math0777@gmail.com          |
|    created: 10.03.2018 22:24              |
"""""""""""""""""""""""""""""""""""""""""""""
# inp = open("input.txt", "r"); input = inp.readline; out = open("output.txt", "w"); print = out.write
TN = 1
from itertools import accumulate
import bisect


# ===========================================


def solution():
    n = int(input())
    v = list(map(int, input().split()))
    t = list(map(int, input().split()))
    ns = [0] * n
    lo = [0] * n
    tt = list(accumulate(t))
    for i in range(n):
        dd = v[i]
        a = 0
        if i != 0:
            dd += tt[i - 1]
            a = tt[i - 1]
        ns[i] += 1
        k = bisect.bisect_right(tt, dd)
        if k < n:
            ns[k] -= 1
    
            lo[k] += v[i] + a
            if k != 0:
                lo[k] -= tt[k - 1]
    ns = list(accumulate(ns))
    for i in range(n):
        lo[i] += t[i] * ns[i]
    print(' '.join(list(map(str, lo))))


# ===========================================
while TN != 0:
    solution()
    TN -= 1
# ===========================================
# inp.close()
# out.close()


import heapq
from bisect import bisect_left, bisect_right
from collections import Counter
from collections import OrderedDict
from collections import deque
from itertools import accumulate, product

import math

R = lambda: map(int, input().split())

n = int(input())
snows = list(R())
melts = list(R())
acc = list(accumulate(melts))
cnt, rem = [0] * n, [0] * n
for i, s in enumerate(snows):
    ri = bisect_right(acc, s + (acc[i - 1] if i > 0 else 0))
    cnt[i] += 1
    if ri < n:
        cnt[ri] -= 1
        rem[ri] += s + (acc[i - 1] if i > 0 else 0) - (acc[ri - 1] if ri > 0 else 0)
cnt = list(accumulate(cnt))
for i in range(n):
    print(melts[i] * cnt[i] + rem[i], end=' ')

import heapq

heap = []

n = int(input())

V = list(map(int, input().split()))

T = list(map(int, input().split()))

tmp = 0

for i in range(n):

    ans = 0

    heapq.heappush(heap, tmp+V[i])

    while len(heap) and heap[0]<=tmp+T[i]:

        ans += heapq.heappop(heap)-tmp

    tmp += T[i]

    ans += T[i]*len(heap)

    print(ans, end=' ')



# Made By Mostafa_Khaled

import heapq

n = int(input())
v = list(map(int, input().split()))
t = list(map(int, input().split()))

q = []
melted = 0
for snow, temp in zip(v, t):
    heapq.heappush(q, snow + melted)
    answer = 0
    while q and q[0] <= melted + temp:
        answer += q[0] - melted
        heapq.heappop(q)
    answer += temp * len(q)
    print(answer, end = ' ')
    melted += temp
    
    
    

import heapq
heap = []
n = int(input())
V = list(map(int, input().split()))
T = list(map(int, input().split()))
tmp = 0
for i in range(n):
    ans = 0
    heapq.heappush(heap, tmp+V[i])
    while len(heap) and heap[0]<=tmp+T[i]:
        ans += heapq.heappop(heap)-tmp
    tmp += T[i]
    ans += T[i]*len(heap)
    print(ans, end=' ')
    
    


from heapq import *
n=int(input())
l=list(map(int,input().split()))
l1=list(map(int,input().split()))
L=[]
heapify(L)
l2=l1[:]
qw=[]
for i in range(1,n) :
    l2[i]+=l2[i-1]
for i in range(n) :
    v=l[i]+l2[i]-l1[i]
    heappush(L,v)
    mi=heappop(L)
    count=0
    while mi<=l2[i] :
        count+=mi-l2[i]+l1[i]
        if not L :
            break
        mi=heappop(L)
        
    else :
        heappush(L,mi)
    ost=count+len(L)*l1[i]
    qw.append(ost)
print(*qw)
    
        
        
    


import sys
# from collections import deque
input=sys.stdin.readline
def binary_search(org,arr,l,r,n,L,value):
	mid=(l+r)//2
	# print(mid,"ppppp")
	if(mid>0 and arr[mid]-value>=org and arr[mid-1]-value<org):
		return mid
	elif(mid==0 and arr[mid]-value>=org ):
		return mid
	elif(mid==L and arr[mid]-value>=org ):
		return mid
	
	elif(mid==n):
		return mid

	elif(mid>0 and arr[mid]-value>org and arr[mid-1]-value>=org):
		return binary_search(org,arr,l,mid,n,L,value)
	
	elif(arr[mid]-value<org):
		# print("dddddd")
		return binary_search(org,arr,mid+1,r,n,L,value)
	return mid
	





n=int(input())
l= list(map(int,input().split())) 
u= list(map(int,input().split())) 
extra=[0]*n
pre=[0]*n
t=[0]*n
t[0]=u[0]
for i in range(1,n):
	t[i]+=t[i-1]+u[i]
# print(t)
for i in range(n):
	if(i>0):
		v=t[i-1]
	else:
		v=0
	index=binary_search(l[i],t,i,n-1,n-1,i,v)
	# print(i,index)
	if(index>0 and index!=i):
		value=t[index]-t[index-1]
		remain=l[i]-(t[index-1]-v)
	elif(index>0 and index==i):
		value=t[index]-t[index-1]
		remain=l[i]


	else:
		value=t[index]
		remain=l[i]
	if(value>=remain):
		extra[index]+=remain
		# print(extra[index],"ooooo")
	elif(remain>value):

		extra[index]+=value
		# print(extra[index],"oooooopp")
	if(i>0 and index>0):
		pre[i-1]-=1
		pre[index-1]+=1
	elif(i==0 and index>0):
		pre[index-1]+=1
	elif(i==0 and index==0):
		continue
	# print(extra,pre)
# print(extra,pre)
for i in range(n-2,-1,-1):
	pre[i]+=pre[i+1]
# print(extra,pre)
r=[0]*n
for i in range(n):
	r[i]=(u[i]*pre[i])+extra[i]
		
for i in r:
	print (i,end=" ")

def findMaxTemp(psT, v, start, minus):
    l = start - 1
    r = len(psT)

    while r - l > 1:
        m = l + (r - l) // 2
        val = psT[m] - minus
        if val < v:
            l = m
        else:
            r = m

    return l, r

def solve():
    N = int(input())
    V = list(map(int, input().split()))
    T = list(map(int, input().split()))

    ans = [0 for _ in range(N)]
    partialAns = [0 for _ in range(N)]
    cnt = [0 for _ in range(N)]
    minus = 0
    psT = T[:]

    for i in range(1, N):
        psT[i] += psT[i - 1]

    for i in range(len(V)):
        l, r = findMaxTemp(psT, V[i], i, minus)

        if r == i:
            partialAns[r] += V[i]
        elif r == len(psT):
            cnt[i] += 1
        else:
            cnt[i] += 1; cnt[l + 1] -= 1
            value = V[i] - (psT[l] - minus)
            partialAns[r] += value

        minus = psT[i]

    for i in range(1, N):
        cnt[i] += cnt[i - 1]

    for i in range(N):
        ans[i] += partialAns[i]
        ans[i] += cnt[i] * T[i]

    return ans

for x in solve():
    print(x, end=' ')

import heapq
heap = []
n = int(input())
V = list(map(int, input().split()))
T = list(map(int, input().split()))
tmp = 0
for i in range(n):
    ans = 0
    heapq.heappush(heap, tmp+V[i])
    while len(heap) and heap[0]<=tmp+T[i]:
        ans += heapq.heappop(heap)-tmp
    tmp += T[i]
    ans += T[i]*len(heap)
    print(ans, end=' ')

from sys import stdin, stdout
import heapq

n = int(input())
v = list(map(int, input().split()))
t = list(map(int, input().split()))

heap = []
sum = 0
for i in range(n):
    ans = 0
    heapq.heappush(heap, sum + v[i])
    while len(heap) and heap[0] <= sum + t[i]:
        ans += heap[0] - sum
        heapq.heappop(heap)
    ans += len(heap) * t[i]
    sum += t[i]
    print(ans, end=' ')

from sys import stdin, stdout
import heapq

n = int(input())
v = list(map(int, input().split()))
t = list(map(int, input().split()))

heap = []
sum = 0
for i in range(n):
    ans = 0
    heapq.heappush(heap, sum + v[i])
    while len(heap) and heap[0] <= sum + t[i]:
        ans += heap[0] - sum
        heapq.heappop(heap)
    ans += len(heap) * t[i]
    sum += t[i]
    print(ans, end=' ')

def bin_search(pref,diff,s,val):
    e = len(pref) - 1
    index = -1
    while s <= e:
        mid = (s + e) >> 1
        if pref[mid] - diff <= val:
            index = mid
            s = mid + 1
        else:
            e = mid - 1
    return index

n = int(input())
a = list(map(int,input().split()))
t = list(map(int,input().split()))
pref = [0 for i in range(len(t))] 
pref[0] = t[0]
for i in range(1,len(t)):
    pref[i] = t[i] + pref[i - 1]

freq = [0 for i in range(len(t))]
ans = [0 for i in range(len(t))]
diff = 0

for i in range(0,n):
    index = bin_search(pref,diff,i,a[i])
    if index == -1:
        ans[i] += a[i]
    else:
        freq[i] += 1
        if index + 1 < n:
            freq[index + 1] -= 1
            ans[index + 1] += (a[i] - pref[index] + diff)
    diff += t[i]

for i in range(1,n):
    freq[i] = freq[i] + freq[i - 1]

for i in range(0,n):
    print(freq[i] * t[i] + ans[i],end = " ")
print()

import sys
input = sys.stdin.readline

def judge(i, x):
    return V[i]-(T_acc[x+1]-T_acc[i])>0

def binary_search(i):
    l, r = 0, N
    
    while l<=r:
        mid = (l+r)//2
        
        if judge(i, mid):
            l = mid+1
        else:
            r = mid-1

    return r

N = int(input())
V = list(map(int, input().split()))
T = list(map(int, input().split()))
T.append(10**18)
T_acc = [0]

for Ti in T:
    T_acc.append(T_acc[-1]+Ti)

last = [0]*(N+1)
imos = [0]*(N+1)

for i in range(N):
    mark = binary_search(i)
    last[mark+1] += V[i]-(T_acc[mark+1]-T_acc[i])
    imos[i] += 1
    imos[mark+1] -= 1

for i in range(N):
    imos[i+1] += imos[i]

for i in range(N):
    ans = imos[i]*T[i]+last[i]
    
    if i<N-1:
        print(ans, end=' ')
    else:
        print(ans)

import heapq
n = int(input())
v = list(map(int, input().split()))
t = list(map(int, input().split()))
d = []
s = 0
for i in range(n):
    ans = 0
    heapq.heappush(d, v[i] + s)
    while d and d[0] <= s + t[i]:
        ans += d[0] - s
        heapq.heappop(d)
    s += t[i]
    ans += len(d) * t[i]
    print(ans, end=' ')


from bisect import *


n = int(input())
h = list(map(int,input().split()))
t = list(map(int,input().split()))

dp 		= [1 for i in range(n+1)]
reminder= [0 for i in range(n+1)]
pre_sum = [0 for i in range(n)]

pre_sum[0] = t[0]

for i in range(1,n):
	pre_sum[i] = pre_sum[i-1] + t[i]


pre = 0

for i in range(n):
	cur   = pre + h[i]
	pre   = pre_sum[i]
	index = bisect(pre_sum,cur)

	
	# try:
	# 	dp[index]-=1
	# except:
	# 	print(i,index,cur)
	dp[index]-=1
	if(index==0):
		reminder[index]+=cur
	else:
		reminder[index] += cur - pre_sum[index-1]
# 	print('index',index)
# 	print('dp',dp)
# 	print('reminder',reminder)

# print(*dp)
# print(*reminder)	


for i in range(1,n):
	dp[i] =dp[i-1]+dp[i]

for i in range(n):
	temp= dp[i]*t[i]+reminder[i]
	print(temp,end=' ')
print()