Cho 1 hoán vị độ dài ~n~ đuợc miêu tả bởi n số nguyên dương ~p_i~.

Do bất cẩn Bob đã đánh mất hoán vị ban đầu, điều duy nhất Bob nhớ đó là các giá tri ~p_i-p_{i-1} | i=2,3,...n~.

Nhiệm vụ của bạn là giúp Bob tìm ra hoán vị ban đầu.

Input

• Dòng đầu tiên gồm số nguyên duơng n.
• Dòng thứ 2 gồm ~n-1~ số nguyên ~q_i~ miêu tả hiệu 2 số liên tiếp trong hoán vị.

Giới hạn:

• ~1\le n \le 10^5~
• ~1-n \le q_i \le n-1~.

Output

• In ra trên một dòng hoán vị ban đầu. Nếu có nhiều dãy số thỏa mãn, in ra kết quả có tổng các phần tử trong dãy là nhỏ nhất.
• Nếu không tồn tại hoán vị nào thỏa mãn in ra -1.

Sample

Input #1

3
-2 1

Output #1

3 1 2

Problem source: CLB Lập Trình PTIT