VNOI Marathon 08

Dancing men

Dancing men is a type of secret code appearing in an adventure of Sherlock Homes. Today, people still use this type of secret code. However, the dancing men is now transmitted via Internet and is more complex to decipher. They will automatically change from time to time to make it harder to recognize from the initial code. The dancing men may have different heights. Each man may turn his head up or down.

For convention, the height of each man is positive if he turns his head up and negative if he turns his head down. After each second, the dancing men are changed as following. Any of three consecutive men are selected. The height of men in the left and right side are added by the signed height of the middle man. Then the middle man turns his head into the opposite direction. The below figure illustrates the changes of three consecutive men:

Initially, all dancing men turn their head up.

Given a sequence of dancing men at some point of time, determine the initial form of them.

Input

• Line 1: a positive integer N that is the number of dancing men in the sequence.
• Line 2: N integers a₁, a₂, a₃, ..., a_n,, in which |a_i| is the i^th man's height at some point of time; a_i > 0 if the man turns his head up and a_i < 0 if the man turns his head down.

The dancing men are numbered as 1 to N from left to right.

Output

Only one line containing:

• A number -1 in case there is no or more than one valid initial sequence of dancing men.
• N integers b₁, b₂, ..., b_n describing the initial sequence of dancing men in the same format as the input. b₁, b₂, ..., b_n should be positive since all men must turn his head up in the beginning.

Constraints

• 1 ≤ N ≤ 10⁵.
• 1 ≤ |a_i| ≤ 5000.

Example

Input
5
2451 -1647 -244 1006 1130

Output
560 244 762 885 245