\(N (1 \le N \le 10^5)\) con bò của nông dân John được xếp thành vòng tròn. Con bò thứ \(i\) có một cái xô có dung tích là số nguyên \(a_i(1 \le a_i \le 10^9)\) lít. Tất cả các thùng ban đầu đều đầy.
Mỗi phút, con bò \(i\) sẽ chuyển tất cả sữa trong thùng của nó cho con bò \(i+1\) với \(1 \le i < N\) , và con bò \(N\) chuyển sữa cho con bò \(1\). Tất cả các quá trình trao đổi diễn ra đồng thời (tức là nếu một con bò có thùng sữa đầy nhưng cho đi \(x\) lít sữa và cũng nhận được \(x\) lít thì sữa của nó được bảo toàn). Nếu tổng lượng sữa của con bò vượt quá \(a_i\), thì lượng sữa dư thừa sẽ bị mất.
Sau mỗi \(1,2,...,N\) phút, tổng số sữa bò còn lại là bao nhiêu?

Input

Dòng đầu chứa số \(N\).
Dòng tiếp theo chứa \(N\) số nguyên \(a_1,a_2,...,a_N\).

Output

In ra \(N\) dòng, trong đó dòng thứ \(i\) là tổng số sữa còn lại của tất cả các con bò sau \(i\) phút.

Scoring

• Subtask \(1\): \(N \le 2000\)
• Subtask \(2\): \(a_i \le 2\)
• Subtask \(3\): Mọi \(a_i\) đều được tạo ra ngẫu nhiên với xác suất như nhau trong khoảng \([1,10^9]\)
• Subtast 4: Không có điều kiện gì thêm.

Example

6
2 2 2 1 2 1

8
7
6
6
6
6

8
3 8 6 4 8 3 8 1

25
20
17
14
12
10
8
8

10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000

2000000053
1000000054
56
49
42
35
28
24
20
20