VNOI Marathon 08

Những hình nhân nhảy múa là một loại mật mã bí ẩn đã xuất hiện trong một câu chuyện về thám tử Sherlock Homes. Ngày nay, người ta vẫn còn dùng loại mật mã này, nhưng các hình nhân được truyền đi bằng hình ảnh qua Internet và khó giải mã hơn. Chúng sẽ tự động biến đổi đi theo thời gian để trở nên khó nhận dạng so với mật mã ban đầu. Các hình nhân có chiều cao khác nhau, mỗi hình nhân có thể quay lên phía trên hoặc quay xuống phía dưới.

Để tiện lợi, ta quy ước chiều cao của mỗi hình nhân là số dương nếu quay đầu lên trên và số âm nếu quay đầu xuống dưới. Sau mỗi giây, các hình nhân sẽ biến đổi như sau. Ba hình nhân liên tiếp bất kỳ sẽ được chọn. Chiều cao của hai hình nhân ở bên trái và phải sẽ được cộng thêm một lượng bằng chiều cao kể cả dấu của hình nhân ở giữa. Sau đó, hình nhân ở giữa sẽ quay ngược đầu lại. Hình dưới đây minh họa sự biến đổi của ba hình nhân liên tiếp:

Biết rằng ban đầu, các hình nhân đều quay lên phía trên.

Biết dãy các hình nhân tại một thời điểm nào đó, bạn hãy xác dịnh dãy hình nhân ban đầu, hoặc thông báo dãy hình nhân không hợp lệ, nếu không tìm được dãy hình nhân ban đầu hoặc dãy hình nhân ban đầu không phải là duy nhất.

Dữ liệu

• Dòng 1: chứa số nguyên dương N, là số lượng hình nhân trên dãy.
• Dòng 2: chứa N số nguyên a₁, a₂, a₃, ..., a_n. Trong đó |a_i| cho biết chiều cao của hình nhân thứ i tại một thời điểm nào đó, a_i > 0 nếu hình nhân quay đầu lên trên, và a_i < 0 nếu hình nhân quay đầu xuống dưới.

Các hình nhân được đánh số thứ tự từ 1 đến N từ trái sang phải.

Kết qủa

Gồm một dòng duy nhất chứa:

• Số -1 nếu không tìm được dãy hình nhân ban đầu hoặc dãy hình nhân ban đầu không phải là duy nhất.
• Hoặc N số nguyên b₁, b₂, ..., b_n là dãy hình nhân ban đầu, với cùng kiểu mô tả như trong dữ liệu vào. b₁, b₂, ..., b_n phải là số nguyên dương, vì các hình nhân ban đầu đều quay lên trên.

Giới hạn

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

Ví dụ

Dữ liệu
5
2451 -1647 -244 1006 1130

Kết quả
560 244 762 885 245