Number Circle

Interview

Time limit1sMemory limit128 MB

Summary

Given a circular array of sums of each element and its two neighbors, reconstruct one valid original positive-integer circular array.

Level: Medium6 of 10
Topics: Math, Simulation, Array
Solved: No attempts yet

Problem

There is a first number circle containing N positive integers in a fixed circular order.

A second number circle is made from it as follows: for every position, add the number at that position and its two adjacent numbers. The resulting sum is written at the same position in the second circle.

You are given the second number circle. Reconstruct and print any possible first number circle.

Input

The first line contains N, the number of values in the second number circle. (3 <= N <= 10,000)

Each of the next N lines contains one value from the second circle, in circular order. Every value is a positive integer less than 10^9.

The first number circle that produces the given second circle may not be unique. However, every input is guaranteed to have at least one answer.

Output

Print N lines: the values in one possible first number circle, in order. Every printed value must be a positive integer.

The circle must not be rotated. The i-th printed value corresponds to the i-th input value. In particular, the sum of the first three printed values must equal the second input value.

Examples3

Example 1
Input
```
3
5
5
5
```
Expected output
```
2
1
2
```
Example 2
Input
```
4
20
15
17
14
```
Expected output
```
5
8
2
7
```
Example 3
Input
```
5
7
8
9
10
11
```
Expected output
```
4
1
3
5
2
```