Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DANCING - Những hình nhân nhảy múa

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 a1, a2, a3, ..., an,, in which |ai| is the ith man's height at some point of time; ai > 0 if the man turns his head up and ai < 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 b1, b2, ..., bn describing the initial sequence of dancing men in the same format as the input. b1, b2, ..., bn should be positive since all men must turn his head up in the beginning.

Constraints

  • 1 ≤ N ≤ 105.
  • 1 ≤ |ai| ≤ 5000.

Example

Input
5
2451 -1647 -244 1006 1130

Output
560 244 762 885 245	

Được gửi lên bởi:VOJ Team
Ngày:2008-07-21
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Nguồn bài:VNOI Marathon '08 - Round 12/DivB
Problem Setter: Ngô Minh Đức

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.