Farmer John đang xếp \(N\) con bò của mình (\(2\le N\le 10^3\)), được đánh số \(1\ldots N\), thành một hàng để chụp ảnh. Ban đầu, FJ dự định con bò thứ \(i\) tính từ bên trái sẽ là con bò mang số \(a_i\), và đã viết hoán vị \(a_1,a_2,\ldots,a_N\) lên một tờ giấy. Không may, tờ giấy đó vừa bị Farmer Nhoj đánh cắp!

May mắn thay, FJ vẫn có thể khôi phục được hoán vị mà ông đã viết ban đầu. Trước khi tờ giấy bị đánh cắp, Bessie đã ghi lại dãy \(b_1,b_2,\ldots,b_{N-1}\) thỏa mãn \(b_i=a_i+a_{i+1}\) với mỗi \(1\le i<N\).

Dựa trên thông tin của Bessie, hãy giúp FJ khôi phục hoán vị \(a\) "nhỏ nhất theo thứ tự từ điển" có thể tạo ra \(b\). Một hoán vị \(x\) nhỏ hơn một hoán vị \(y\) theo thứ tự từ điển nếu tồn tại một chỉ số \(j\) sao cho \(x_i=y_i\) với mọi \(i<j\) và \(x_j<y_j\) (nói cách khác, hai hoán vị giống hệt nhau cho đến một vị trí nào đó, và tại vị trí ấy \(x\) nhỏ hơn \(y\)). Đề bài đảm bảo tồn tại ít nhất một hoán vị \(a\) như vậy.

Phân nhóm

• Các test từ \(2\) đến \(4\) thỏa mãn \(N\le 8\).
• Các test từ \(5\) đến \(10\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp photo.in.

Dòng đầu tiên chứa một số nguyên \(N\).

Dòng thứ hai chứa \(N-1\) số nguyên \(b_1,b_2,\ldots,b_{N-1}\), cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra tệp photo.out một dòng gồm \(N\) số nguyên \(a_1,a_2,\ldots,a_N\), cách nhau bởi dấu cách.

Ví dụ

5
4 6 7 6

3 1 5 2 4

Nguồn

• Kỳ thi: USACO 2020 January Contest, Bronze
• Tên bài: Photoshoot
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=988
• Tác giả đề: Benjamin Qi và Chris Zhang