Problem Description

Xiao A had a hallucination in class. He imagined several sinks arranged in a circle, where the water in each sink would flow into the next sink (of course, this is impossible in real life).

So Xiao A started thinking about the following problem:

There are $n$ sinks arranged in a circle. Each sink has a capacity, and initially all sinks are full. Then, every second, all the water in sink $i$ is transferred to sink $i+1$ (in particular, the water in sink $n$ is transferred to sink $1$). If the transferred water exceeds the capacity, it will overflow.

Now he wants to know, for the next $1$ to $n$ seconds, the total amount of water in all sinks at each second.

Input Format

The first line contains a positive integer $n\ (1\le n\le 10^5)$, representing the number of sinks.

The second line contains $n$ numbers. The $i$-th number $a_i\ (1\le a_i\le 10^9)$ represents the capacity of sink $i$.

Output Format

Output $n$ numbers separated by spaces. They represent, for seconds $1$ to $n$, the total amount of water in all sinks at each second.

5
3 2 5 4 3

14 12 11 10 10

6
171 814 2313 6676 196 897

3861 1719 1076 1051 1026 1026

Hint

Translated by ChatGPT 5