Farmer John 的 $N$（$1\le N \le 5\cdot 10^5$）头奶牛排成一圈。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\le a_i\le 10^9$）升的桶。所有桶初始时都是满的。 每一分钟，对于 $1\le i< N$，奶牛 $i$ 会将其桶中所有牛奶传递给奶牛 $i+1$，奶牛 $N$ 将其牛奶传递给奶牛 $1$。所有交换同时发生（即，如果一头奶牛的桶是满的，送出 $x$ 升牛奶同时收到 $x$ 升，则她的牛奶量保持不变）。如果此时一头奶牛的牛奶量超过 $a_i$，则多余的牛奶会损失。 在 $1,2,\ldots,N$ 的每一分钟后，所有奶牛总共还余下多少牛奶？

输入的第一行包含 $N$。 第二行包含 $a_1,a_2,\ldots,a_N$。

输出 $N$ 行，其中第 $i$ 行包含 $i$ 分钟后所有奶牛总共余下的牛奶量。