Жучко наредил во круг N кофи комплетно полни со млеко. Кофите се означени по редослед со броевите од 1 до N, и за секоја од нив го знаеме капацитетот A_i во литри. Според ова, веднаш после кофата i е кофата i + 1 за секое i < N, а после кофата N е кофата 1. На крај тој додал една помошна празна кофа, со капацитет поголем од кофата N, помеѓу кофите N и 1.

Сега Жучко сака да си игра, па следниот процес ќе го направи N пати:
Го претура целото млеко од N-тата кофа во помошната. Потоа млекото од (N-1)-та кофа во N-тата, па од (N-2)-та во (N-1)-та и се' така до претурање на млекото од првата во втората кофа. На крај го претура млекото од помошната во првата кофа. Со ова тој прави еден цел „круг претурања“.

Се разбира, ако претураме од помала во поголема кофа нема проблем, ама ако претураме од поголема во помала, откако ќе се исполни помалата кофа останатото млеко ќе се истури и ќе биде изгубено. Со тоа, после секој круг претурања најверојатно ќе има загуба на млеко.

Ваша задача е да отпечатите колку вкупно литри млеко има во кофите после секој од N-те кругови претурања, во редослед од првиот круг до последниот.

Влез

Во првиот ред е даден цел број N (1 ≤ N ≤ 500 000) - бројот на кофи.
Во вториот ред се дадени N цели броеви A_i (1 ≤ A_i ≤ 1 000 000 000).

Забелешка.
За 31 поен: 1 ≤ N ≤ 2 000.
За следни 30 поени: 1 ≤ A_i ≤ 2.
За следни 30 поени: броевите A_i се случајно избрани (независно еден од друг).

Излез

Отпечатете ги бараните N броеви, секој во посебен ред.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
6
2 2 2 1 2 1

излез
8 
7 
6 
6 
6 
6