問題文

パズルゲーマーの茜ちゃんと葵ちゃんは、お揃いのスライドパズルを入手したいです。

整数 $N$ と $N$ 次正方行列 $A$ が与えられます。また、 $N$ 次正方行列 $X$ があり、はじめ $X_{i, j} = (i - 1) N + (j - 1)$ です。

$X_{i, j} = 0$ となる $(i, j)$ とそれに隣接する $(i', j')$ を選び、 $X_{i, j}$ と $X_{i', j'}$ を swap することをスライド操作と定義します。
ここで $(i, j)$ と $(i', j')$ が隣接するとは、$|i - i'| + |j - j'| = 1$ を満たすことをいいます。

また、$N$ 次正方行列 $M$ に対する楽しさを、 $\displaystyle \sum_{i = 1}^N \sum_{j = 1}^N (A_{i, j} \times M_{i, j})$ と定義します。

以下の条件をすべて満たす $N$ 次正方行列の組 $(P, Q)$ が存在するか判定し、存在するならば $1$ つ提示してください。

• $P \ne Q$
• $X$ に対しスライド操作を $0$ 回以上の好きな回数繰り返すことで、$X = P$ にすることが可能である。
• $X$ に対しスライド操作を $0$ 回以上の好きな回数繰り返すことで、$X = Q$ にすることが可能である。
• $P$ の楽しさと $Q$ の楽しさは等しい。

制約

• $2 \le N \le 500$
• $1 \le A_{i, j} \le 10^8$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$N$
$A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, N}$
$A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, N}$
$\vdots$
$A_{N, 1}$ $A_{N, 2}$ $\cdots$ $A_{N, N}$

出力

条件をすべて満たす $N$ 次正方行列の組 $(P, Q)$ が存在しなければ、 No とのみ出力してください。

存在するならば、$(P, Q)$ を以下の形式で出力してください。答えが複数存在する場合、いずれを出力しても正解と判定されます。

Yes
$P_{1, 1}$ $P_{1, 2}$ $\cdots$ $P_{1, N}$
$P_{2, 1}$ $P_{2, 2}$ $\cdots$ $P_{2, N}$
$\vdots$
$P_{N, 1}$ $P_{N, 2}$ $\cdots$ $P_{N, N}$
$Q_{1, 1}$ $Q_{1, 2}$ $\cdots$ $Q_{1, N}$
$Q_{2, 1}$ $Q_{2, 2}$ $\cdots$ $Q_{2, N}$
$\vdots$
$Q_{N, 1}$ $Q_{N, 2}$ $\cdots$ $Q_{N, N}$

サンプル

2
1 2
3 4

Yes
0 2 
3 1 
0 3 
1 2

3
1 10 100
1000 10000 100000
1000000 10000000 100000000

No

5
2 13 31 51 71
3 17 37 53 73
5 19 41 59 83
7 23 43 61 89
11 29 47 67 97

Yes
0 18 21 12 11
7 15 10 16 5
4 13 6 14 24
8 2 9 22 1
17 3 20 19 23
2 19 10 5 22
15 23 9 14 18
6 11 8 13 20
3 1 0 7 21
16 12 24 4 17