부등호 퍼즐

부등호 퍼즐은 $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$