爱丽丝非常喜欢雪!不幸的是,今年的冬天已经结束了,她不能再指望再过冬天了。鲍勃因此给她买了一份礼物——一台大型造雪机。他计划每天造一些雪。第一天,他会堆一堆第六卷的雪,放在她的花园里。
每一天,每堆都会因融化而收缩一点。更准确地说,当某一天的温度为Ti时,每堆的体积都会减少Ti。如果这会将一堆体积减少到零或以下,那么它就会永远消失。所有雪堆都是相互独立的。
请注意,第 i 天生成的堆在同一天已经损失了部分体积。在极端情况下,这可能意味着在特定一天结束时没有剩下任何堆。
您将获得初始堆大小和每天的温度。确定每天的融雪总量。
输入
第一行包含一个整数 N (1 ≤ N ≤ 105) — 天数。
第二行包含 N 个整数 V1, V2, ..., VN (0 ≤ Vi ≤ 109),其中 Vi 是第 i 天形成的雪堆的初始大小。
第三行包含 N 个整数 T1, T2, ..., TN (0 ≤ Ti ≤ 109),其中 Ti 是第 i 天的温度。
输出
输出一行包含 N 个整数,其中第 i 个整数表示第 i 天的融雪总量。
示例
输入 #1
3 10 10 5 5 7 2
输出 #1
5 12 4
输入 #2
5 30 25 20 15 10 9 10 12 4 13
输出 #2
9 20 35 11 25
注意
在第一个示例中,Bob 首先制作了一个体积为 10 的雪堆,该雪堆在同一天融化到了 5 的大小。第二天,他又堆了一堆10号的。由于天气比前一天暖和一些,第一堆完全消失了,而第二堆则缩小到了3号。第二天结束时,他只剩下一堆3号的。第三天,他堆了比平时更小的堆,但随着气温也下降,两堆都保存到了当天结束。