题目描述

有一个 $n\times n$ 矩阵 $A$，其中恰好填入 $1,2,\ldots,n^2$，每个数出现一次。

对每个位置 $(i,j)$ 定义：

• $top_{i,j}$：同一列中位于 $(i,j)$ 上方、且数值大于 $A_{i,j}$ 的元素个数；
• $left_{i,j}$：同一行中位于 $(i,j)$ 左侧、且数值大于 $A_{i,j}$ 的元素个数。

现在给出矩阵 top 和 left，请构造任意一个满足条件的矩阵 $A$。如果不存在合法矩阵，输出 0。

输入格式

第一行一个整数 $n$，$1\le n\le600$。

接下来 $n$ 行给出矩阵 top，每行 $n$ 个非负整数。

随后给出矩阵 left，同样为 $n$ 行、每行 $n$ 个非负整数。原题两矩阵之间可能有一个空行，普通空白读取均可。

所有给出的数均不超过 $n$。

输出格式

如果不存在答案，输出一行：

0

否则输出 $n$ 行，每行 $n$ 个整数，构成一个 $1\ldots n^2$ 的排列矩阵，并满足给定的 top 与 left。

如果有多种答案，输出任意一种。本题使用特殊判题。

样例

3
0 0 0
0 0 0
0 0 2

0 0 0
0 1 0
0 1 2

一种合法输出为：

1 2 6
5 3 7
9 8 4