Farmer John xếp $N$ cô bò ($2\le N\le 10^3$), đánh số $1\ldots N$, thành hàng để chụp ảnh. FJ định cho cô thứ $i$ từ trái là cô mang số $a_i,$ và ghi hoán vị $a_1,a_2,\ldots,a_N$ lên giấy. Tiếc rằng Farmer Nhoj vừa đánh cắp tờ giấy!

May thay, FJ vẫn có thể khôi phục hoán vị đã ghi. Trước khi giấy bị lấy, Bessie ghi dãy $b_1,b_2,\ldots,b_{N-1}$ thỏa $b_i=a_i+a_{i+1}$ với mọi $1\le i<N.$

Dựa vào thông tin của Bessie, 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$. Hoán vị $x$ nhỏ hơn $y$ theo thứ tự từ điển nếu tồn tại $j$ sao cho $x_i=y_i$ với mọi $i<j$ và $x_j<y_j$ (tức hai hoán vị giống nhau tới một vị trí, tại đó $x$ nhỏ hơn $y$). Bảo đảm tồn tại ít nhất một $a$ như vậy.

Dữ liệu vào

Dòng đầu 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

Một dòng chứa $N$ số nguyên $a_1,a_2,\ldots,a_{N}.$ cách nhau bởi dấu cách.

Ví dụ

Dữ liệu vào 1

5
4 6 7 6

Dữ liệu ra 1

3 1 5 2 4

Ghi chú

$a$ tạo ra $b$ vì $3+1=4$, $1+5=6$, $5+2=7$ và $2+4=6.$

Nhiệm vụ con

• Các trường hợp thử $2$–$4$ thỏa $N\le 8.$

• Các trường hợp thử $5$–$10$ không có ràng buộc thêm.

Tác giả bài toán: Benjamin Qi và Chris Zhang