Given a non-negative integer array $f$ of length $n-1$. We define $d_{i,j} = \min_{k=i}^j f_k$. Also, for any $1 \le i \le n$, we define $f'_{i} = \sum_{j=1}^{i-1} d_{j,i-1} + \sum_{j=i}^{n-1} d_{i,j}$.

You are given the values $f'_1, f'_2, \dots, f'_n$. You need to determine whether there exists a corresponding non-negative integer array $f$ of length $n-1$ that satisfies the above conditions.

Input

The first line contains an integer $n$.

The second line contains $n$ non-negative integers, representing $f'_1, f'_2, \dots, f'_n$ respectively.

Output

If a non-negative integer array $f$ satisfying the conditions exists:

Output 'Yes' on the first line, and output $n-1$ non-negative integers on the second line, where the $i$-th integer represents $f_i$.

If no such non-negative integer array $f$ exists:

Output 'No' on the first line.

Examples

Input 1

3
2 3 3

Output 1

Yes
1 2

Subtasks

For all data, $1 \le n \le 80$ and $0 \le f'_i \le 10^8$.

• Subtask 1 (11 pts): $n \le 5$, satisfies Property A.
• Subtask 2 (15 pts): $n \le 8$.
• Subtask 3 (13 pts): $n \le 14$.
• Subtask 4 (25 pts): $n \le 50$, satisfies Property B.
• Subtask 5 (17 pts): $n \le 50$.
• Subtask 6 (19 pts): No special restrictions.

Property A: Guaranteed that if a valid solution exists, there exists at least one valid solution where all numbers are less than $20$.

Property B: Guaranteed that if a valid solution exists, there exists at least one valid solution where all numbers are less than $50$.