题目描述

迎新春，伴随的是喜悦与祝福，所以这道题非常简单，以祝所有的 OIer 在新的一年各种赛事里 rp++。（新年礼物 Ⅱ 为本题的提高版）

新年必不可少的是串门送礼，@zls_XICK 收到了来自 $N$ 位朋友的 $N$ 个礼物，每个礼物都会给他带来祝福，第 $i$ 个礼物的祝福值为 $a_i$，这些礼物排成环状，也就是第 $1$ 个礼物与第 $N$ 个礼物相接，礼物似乎蕴含着一些魔力，它们摆放在一起时祝福值会累加，累加的规则如下：

• 第 $i$ 个礼物会增加其左右两边相邻的两个礼物的祝福值，也就是累加后的祝福值 $a'_i=a_{i-1}+a_i+a_{i+1}$，而首尾两个礼物则也会增加对方的祝福值。

• 此外，这些礼物累加祝福值是同时的，也就是不存在一个礼物先累加后另一个礼物才累加，同时，如果一个礼物两侧是同一个礼物，那么它只会累加一次，礼物也不会累加自己的祝福值。

现在 @zls_XICK 想知道这些礼物祝福值累加后分别是多少。

输入格式

输入包括两行。

第一行输入一个整数 $N$ 表示礼物个数。

第二行输入 $N$ 个整数表示第 $1$~$N$ 个礼物的祝福值 $a_1$~$a_N$。

输出格式

输出一行 $N$ 个整数。

第 $i$ 个整数表示第 $i$ 个礼物累加后的祝福值 $a'_i$。

4
1 2 3 4

7 6 9 8

1
1

1

2
1 2

3 3

数据规模与约定

对于 $40\%$ 的数据满足 $1 \le N \le 10^3$。

对于 $100\%$ 的数据满足 $1 \le N \le 10^6,1 \le a_i \le 10^7$。