Khôi phục hoán vị từ dãy hiệu

Một mảng số nguyên $p_1,p_2,\dots ,p_n$ được gọi là một hoán vị nếu nó chứa mỗi số từ $1$ đến $n$ đúng một lần. Ví dụ, $[3,1,2]$, $[1]$, $[1,2,3,4,5]$ và $[4,3,1,2]$ là các hoán vị; còn $[2]$, $[1,1]$, $[2,3,4]$ thì không.

Cho trước số nguyên $n$ và mảng $q_1,q_2,\dots ,q_{n-1}$ trong đó $q_i=p_{i+1}-p_i$, hãy khôi phục lại hoán vị $p$ ban đầu, hoặc khẳng định không tồn tại hoán vị nào tương ứng.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — độ dài hoán vị cần khôi phục.
• Dòng thứ hai chứa $n-1$ số nguyên $q_1,q_2,\dots ,q_{n-1}$.

Dữ liệu ra

In ra $-1$ nếu không tồn tại hoán vị $p$ độ dài $n$ thỏa mãn dãy $q$ đã cho. Ngược lại, in ra $n$ số $p_1,p_2,\dots ,p_n$ cách nhau bởi dấu cách. Nếu có nhiều hoán vị thỏa mãn, in ra hoán vị bất kỳ.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $-n<q_i<n$

Ví dụ