atcoder#ARC115B. [ARC115B] Plus Matrix

[ARC115B] Plus Matrix

Score : 400400 points

Problem Statement

Given is an N×NN \times N matrix CC whose elements are non-negative integers. Determine whether there is a pair of sequences of non-negative integers A1,A2,,ANA_1,A_2,\ldots,A_N and B1,B2,,BNB_1,B_2,\ldots,B_N such that Ci,j=Ai+BjC_{i,j}=A_i+B_j for every (i,j)(i, j). If the answer is yes, print one such pair.

Constraints

  • 1N5001 \leq N \leq 500
  • 0Ci,j1090 \leq C_{i,j} \leq 10^9

Input

Input is given from Standard Input in the following format:

NN

C1,1C_{1,1} C1,2C_{1,2} \ldots C1,NC_{1,N}

C2,1C_{2,1} C2,2C_{2,2} \ldots C2,NC_{2,N}

::

CN,1C_{N,1} CN,2C_{N,2} \ldots CN,NC_{N,N}

Output

  • If no pair A,BA, B satisfies the condition:

Print No in the first line.

No

  • If some pair A,BA, B satisfies the condition:

In the first line, print Yes. In the second line, print the elements of AA, with spaces in between. In the third line, print the elements of BB, with spaces in between.

If multiple pairs satisfy the condition, any of them will be accepted.

Yes

A1A_1 A2A_2 \ldots ANA_N

B1B_1 B2B_2 \ldots BNB_N

3
4 3 5
2 1 3
3 2 4
Yes
2 0 1
2 1 3

Note that AA and BB consist of non-negative integers.

3
4 3 5
2 2 3
3 2 4
No