D - 水流入水坝

得分 : $400$ 分

问题描述

有 $N$座山组成一个环，依次称为山$1$、山$2$、...、山$N$，顺时针编号。 $N$ 是一个奇数。

在这些山之间，有 $N$ 座水坝，分别称为水坝$1$、水坝$2$、...、水坝$N$。 第 $i$ 座水坝（$1 \leq i \leq N$）位于山 $i$ 和 $i+1$ 之间（山 $N+1$ 是山 $1$）。

当第 $i$ 座山山头接收到 $2x$ 升的雨水时，第 $i-1$ 座水坝和第 $i$ 座水坝都各自蓄积 $x$ 升的水（水坝 $0$ 是水坝 $N$）。

有一天，每座山山头都接收到了一个非负偶数升雨水。

结果是，第 $i$ 座水坝（$1 \leq i \leq N$）积累了总共 $A_i$ 升的水。

请找出每座山山头接收到的雨水量。 在本问题的限制条件下，我们可以证明解是唯一的。

限制条件

• 输入中的所有值都是整数。
• $3 \leq N \leq 10^5\!-\!1$
• $N$是奇数。
• $0 \leq A_i \leq 10^9$
• 在每座山头接收到一个非负偶数升雨水的情况下，输入所表示的情况是可以发生的。

输入

输入以以下格式从标准输入中给出：

$N$

$A_1$ $A_2$ ... $A_N$

输出

按顺序输出 $N$ 个整数，表示每座山山头接收到的雨水量。

样例输入1

3
2 2 4

样例输出1

4 0 4

如果我们假设山$1$、山$2$和山$3$分别接收到 $4$、$0$ 和 $4$ 升的雨水，与输入一致，情况如下：

• 水坝$1$ 应该累积了 $\frac{4}{2} + \frac{0}{2} = 2$ 升的水。
• 水坝$2$ 应该累积了 $\frac{0}{2} + \frac{4}{2} = 2$ 升的水。
• 水坝$3$ 应该累积了 $\frac{4}{2} + \frac{4}{2} = 4$ 升的水。

样例输入2

5
3 8 7 5 5

样例输出2

2 4 12 2 8

样例输入3

3
1000000000 1000000000 0

样例输出3

0 2000000000 0