부등호 퍼즐

부등호 퍼즐은 $1$부터 $N^2$까지의 정수를 모두 이용하여 $N \times N$ 격자판을 채우는 퍼즐이다. 격자 칸 사이에는 부등호가 그려져 있으며, 인접한 두 칸의 정수가 이 대소 관계를 만족해야 한다. 예를 들어 다음과 같은 $3 \times 3$ 부등호 퍼즐이 주어졌다고 하자.

왼쪽 위 칸을 보자. 가로로 인접한 칸 사이와 세로로 인접한 칸 사이에 부등호가 적혀 있다. 주어진 대소 관계를 모두 만족하도록 칸에 정수를 채울 수 있다.

이처럼 대소 관계를 지키면서 $1$부터 $9$까지의 모든 정수를 사용해 퍼즐을 완성할 수 있다.

$N \times N$ 부등호 퍼즐이 주어질 때 퍼즐의 해답을 출력하는 프로그램을 작성하라. 가능한 답이 여러 가지라면 그중 아무거나 하나를 출력한다.

첫 번째 줄에 $N$이 주어진다.

편의상 $N \times N$ 격자판을 다음과 같은 행렬로 나타내자.

$\begin{matrix} A_{1,1} & A_{1,2} & A_{1,3} & \ldots & A_{1,N}\\ A_{2,1} & A_{2,2} & A_{2,3} & \ldots & A_{2,N}\\ A_{3,1} & A_{3,2} & A_{3,3} & \ldots & A_{3,N}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ A_{N,1} & A_{N,2} & A_{N,3} & \ldots & A_{N,N} \end{matrix}$

두 번째 줄부터는 가로로 인접한 격자 칸이 만족해야 하는 대소 관계를 나타내는 $N \times (N-1)$ 크기의 부등호 행렬 $R$이 주어진다.

$\begin{matrix} R_{1,1} & R_{1,2} & R_{1,3} & \ldots & R_{1,N-1}\\ R_{2,1} & R_{2,2} & R_{2,3} & \ldots & R_{2,N-1}\\ R_{3,1} & R_{3,2} & R_{3,3} & \ldots & R_{3,N-1}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ R_{N,1} & R_{N,2} & R_{N,3} & \ldots & R_{N,N-1} \end{matrix}$

부등호 행렬의 원소 $R_{r,c}$는 < 또는 >이며, 각각의 뜻은 다음과 같다.

• <이면 $A_{r,c} < A_{r,c+1}$을 만족해야 한다.
• >이면 $A_{r,c} > A_{r,c+1}$을 만족해야 한다.

이어서 세로로 인접한 격자 칸이 만족해야 하는 대소 관계를 나타내는 $(N-1) \times N$ 크기의 부등호 행렬 $C$가 주어진다.

$\begin{matrix} C_{1,1} & C_{1,2} & C_{1,3} & \ldots & C_{1,N}\\ C_{2,1} & C_{2,2} & C_{2,3} & \ldots & C_{2,N}\\ C_{3,1} & C_{3,2} & C_{3,3} & \ldots & C_{3,N}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ C_{N-1,1} & C_{N-1,2} & C_{N-1,3} & \ldots & C_{N-1,N} \end{matrix}$

부등호 행렬의 원소 $C_{r,c}$는 < 또는 >이며, 각각의 뜻은 다음과 같다.

• <이면 $A_{r,c} < A_{r+1,c}$을 만족해야 한다.
• >이면 $A_{r,c} > A_{r+1,c}$을 만족해야 한다.

항상 풀이가 존재하는 입력이 주어진다.

$N$개의 줄에 걸쳐 정수 $N$개를 공백으로 구분하여 출력한다. $i$번째 줄의 $j$번째 수는 $A_{i,j}$에 적힐 정수이다.

$2 \le N \le 1{,}000$