Юра обожает зиму. Больше всего он в восторге от льда. Но зима закончилась и Юре придется ждать следующей. Чтобы Юра не огорчался, обезьянка подарила ему ледовую машину. Устройство производит определенное количество льда каждый день. В начале дня номер i создается vi килограммов льда и Юрий ставит этот лед на подоконник.

Но не все так просто. Каждый день лед на подоконнике тает. А именно, если днем температура равна x, то все существующие куски льда уменьшаются на x. Если в определенный момент масса куска льда равна 0, то кусок исчезает. Каждый кусок тает независимо от другого.

Обратите внимание на то, что сугроб, изготовленный в день i, также теряет часть своей массы в этот же день.

Вам заданы начальные массы каждого куска льда, а также температура на каждый день. Для каждого дня определите суммарную массу растаявшего льда.

Входные данные

Первая строка содержит количество дней n (1 ≤ n ≤105). Вторая строка содержит n целых чисел - массу куска, сделанного в день i. В третьей строке задано n целых чисел - температура в день i. Все входные данные неотрицательны. Масса и температура не превышают 109.

Выходные данные

Выведите одну строку из n чисел, где i-тое число обозначает общую массу льда, который растает в день i.