Description

农夫约翰的$N\left(1 \leq N \leq 5 \cdot 10^5\right)$头奶牛排成一个圆圈。第$i$头奶牛有一个整数容量的桶$a_i\left(1 \leq a_i \leq 10^9\right)$升。所有桶最初都是满的。

每分钟，第$i$头奶牛将其桶中的所有牛奶传递给第$i+1$头奶牛，$1 \leq i<N$，第$N$头奶牛将其牛奶传递给第1头奶牛。所有交换同时发生（即，如果一头奶牛有一个满桶但是给出$x$升牛奶并且也收到$x$升，她的牛奶将得到保留）。

如果一头奶牛的总牛奶量超过了$a_i$，那么多余的牛奶将会丢失。

在每个$1,2, \ldots, N$分钟后，所有奶牛中剩下多少总牛奶？

Format

输入格式：

第一行包含$N$。

接下来的一行包含整数$a_1, a_2, \ldots, a_N$。

输出格式：

输出$N$行，第$i$行是$i$分钟后所有奶牛中剩余的总牛奶量。

Samples

6
2 2 2 1 2 1

8
7
6
6
6
6

初始时，每个桶中的牛奶量为$[2,2,2,1,2,1]$。

• 经过1分钟后，每个桶中的牛奶量为$[1,2,2,1,1,1]$，因此总牛奶量为8。
• 经过2分钟后，每个桶中的牛奶量为$[1,1,2,1,1,1]$，因此总牛奶量为7。
• 经过3分钟后，每个桶中的牛奶量为$[1,1,1,1,1,1]$，因此总牛奶量为6。
• 经过4分钟后，每个桶中的牛奶量为$[1,1,1,1,1,1]$，因此总牛奶量为6。
• 经过5分钟后，每个桶中的牛奶量为$[1,1,1,1,1,1]$，因此总牛奶量为6。
• 经过6分钟后，每个桶中的牛奶量为$[1,1,1,1,1,1]$，因此总牛奶量为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

Limitation

• 输入4-5：$N \leq 2000$
• 输入6-8：$a_i \leq 2$
• 输入9-13：所有的$a_i$都在范围$\left[1,10^9\right]$内均匀随机生成。
• 输入14-23：没有额外的约束。