Problem Description

During class, Little A experiences a hallucination where he imagines several sinks arranged in a circular pattern, each transferring its water to the next sink (which is impossible in reality).

Little A then contemplates the following problem:

There are \( n \) sinks arranged in a circle, each with a certain capacity, and initially filled to the brim. Every second, the water in sink \( i \) is completely transferred to sink \( i+1 \) (with the water from the \( n \)-th sink transferring to the first). If the transferred water exceeds the capacity, it overflows.

He wants to know the total amount of water in all sinks for each second from 1 to \( n \).

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, where 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, representing the total amount of water in all sinks for each second from 1 to \( n \).

Sample Input and Output

Sample Input #1

5
3 2 5 4 3

Sample Output #1

14 12 11 10 10

Sample Input #2

6
171 814 2313 6676 196 897

Sample Output #2

3861 1719 1076 1051 1026 1026

见题面 Input 部分

见题面 Output 部分