You are given a grid ~d~ of size ~N \times (N-1)~.

Using this grid, you are to generate a new grid ~a~ of size ~N \times N~ as follows:

1. The first element in each row ~i~ will be assigned a value of ~v_i~. The array ~v~ is unknown to you.
2. For each element ~2 \le j \le N~ in row ~i~, ~a_{i,j} = a_{i, j-1} + d_{i, j-1}~.

A third array, ~k~ will then be generated as follows:

1. The ~i^\text{th}~ element is the median of the ~i^\text{th}~ column in ~a~.

It is known that the median of the array ~k~ is exactly zero. Can you determine any array ~v~ that makes the median of ~k~ zero, or state that it is impossible?

Note: For odd ~N~, the median of the array is the middle element in the sorted array. For even ~N~, the median is the minimum of the two middle elements in the sorted array. For example, the median of ~[1, 6, 4, 3]~ is ~3~.

Input Specification

The first line will contain the integer ~N~ ~(2 \le N \le 1000)~.

The next ~N~ lines will each contain ~N-1~ integers, ~d_{i,j}~ ~(|d_{i,j}| \le 10^5)~.

Output Specification

If it is impossible, print NO on one line.

Otherwise, print YES on the first line.
On the second line, print ~N~ space separated integers, the array ~v~. ~v_i~ must fit in a 32-bit integer ~(-2^{31} \le v_i < 2^{31})~, or you will receive Wrong Answer.

Subtasks

Subtask 1 [7%]

~N \le 5, d_{i,j} \ge 0~

Subtask 2 [24%]

~d_{i,j} \ge 0~

Subtask 3 [69%]

No additional constraints.

Sample Input for Subtask 1

4
2 1 0
3 3 0
1 6 1
1 1 1

Sample Output for Subtask 1

YES
-1 -3 -2 0

Explanation for Sample for Subtask 1

The array ~a~ that is generated with the array ~k~ below is:

-1  1  2  2
-3  0  3  3
-2 -1  5  6
 0  1  2  3
-----------
-2  0  2  3

The median of the array ~k~ is ~0~. Note that there could be multiple answers. For example, ~[-2, -3, -3, 0]~ is also an answer. You are only required to print any one of them.

Sample Input for Subtask 2

7
1 2 2 2 1 1
3 0 0 1 1 1
0 0 0 0 0 0
1 0 2 1 0 1
2 0 0 1 4 0
2 1 1 2 4 5
1 1 1 1 1 1

Sample Output for Subtask 2

YES
5 1 -2 -3 1 -5 -8

Sample Input for Subtask 3

3
3 -12
-6 3
6 -5

Sample Output for Subtask 3

YES
-1 5 -1