Алиса обожает снег! К сожалению, этой зиме уже пришел конец (мы надеемся), и Алисе придется ждать до следующей зимы. Чтобы порадовать Алису, Боб купил ей подарок — большой генератор снега. Он планирует производить некоторое количество снега каждый день. Утром дня номер i он сделает отдельный сугроб объема Vi в саду Алисы.
Каждый день каждый существующий сугроб немного уменьшается в размерах из-за таяния. А именно, если температура в некоторый день равна Ti, то каждый существующий сугроб уменьшит свой объем на Ti. Если в результате этого объем уменьшится до нуля, то сугроб полностью исчезнет. Все сугробы тают независимо друг от друга.
Обратите внимание, что сугроб, произведенный в день i, тоже теряет часть своего объема в этот день. В том числе возможно такое, что в конце некоторых дней нет ни одного сугроба снега.
Вам даны изначальные размеры сугробов и температура в каждый из дней. Определите общий объем растаявшего снега в каждый из дней.
Выходные данные
Выведите одну строку с N целыми числами, где i-е число будет обозначать общий объем снега, растаявшего в день номер i.
Примечание
В первом примере Боб сначала сделает сугроб объема 10, который растает до размера 5 в тот же день. Во второй день он сделает еще один сугроб объема 10. Так как в этот день немного теплее, первый сугроб растает до конца, а второй сугроб уменьшится до размера 3. В конце второго дня останется только один сугроб размера 3. В третий день Боб сделает сугроб меньше, чем обычно, но, поскольку температура тоже уменьшилась, до конца дня доживут оба сугроба.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10 10 5
5 7 2
|
5 12 4
|
|
2
|
5
30 25 20 15 10
9 10 12 4 13
|
9 20 35 11 25
|