D - Rain Flows into Dams

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

円形に N 個の山が連なっており、時計回りに山 1, 山 2, , 山 N と呼ばれます。N奇数です。

これらの山の間に N 個のダムがあり、ダム 1, ダム 2, , ダム N と呼ばれます。ダム i (1 \leq i \leq N) は山 i と山 i+1 の間にあります (山 N+1 は山 1 のことを指します)。

i (1 \leq i \leq N) に 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

出力

1, 山 2, , 山 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

Score : 400 points

Problem Statement

There are N mountains in a circle, called Mountain 1, Mountain 2, ..., Mountain N in clockwise order. N is an odd number.

Between these mountains, there are N dams, called Dam 1, Dam 2, ..., Dam N. Dam i (1 \leq i \leq N) is located between Mountain i and i+1 (Mountain N+1 is Mountain 1).

When Mountain i (1 \leq i \leq N) receives 2x liters of rain, Dam i-1 and Dam i each accumulates x liters of water (Dam 0 is Dam N).

One day, each of the mountains received a non-negative even number of liters of rain.

As a result, Dam i (1 \leq i \leq N) accumulated a total of A_i liters of water.

Find the amount of rain each of the mountains received. We can prove that the solution is unique under the constraints of this problem.

Constraints

  • All values in input are integers.
  • 3 \leq N \leq 10^5-1
  • N is an odd number.
  • 0 \leq A_i \leq 10^9
  • The situation represented by input can occur when each of the mountains receives a non-negative even number of liters of rain.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print N integers representing the number of liters of rain Mountain 1, Mountain 2, ..., Mountain N received, in this order.


Sample Input 1

3
2 2 4

Sample Output 1

4 0 4

If we assume Mountain 1, 2, and 3 received 4, 0, and 4 liters of rain, respectively, it is consistent with this input, as follows:

  • Dam 1 should have accumulated \frac{4}{2} + \frac{0}{2} = 2 liters of water.
  • Dam 2 should have accumulated \frac{0}{2} + \frac{4}{2} = 2 liters of water.
  • Dam 3 should have accumulated \frac{4}{2} + \frac{4}{2} = 4 liters of water.

Sample Input 2

5
3 8 7 5 5

Sample Output 2

2 4 12 2 8

Sample Input 3

3
1000000000 1000000000 0

Sample Output 3

0 2000000000 0