수 사각형

수 사각형(Number Square) 은 $1, 2, \ldots, N$ 의 수를 $N \times N$ 격자에 채워 넣는 퍼즐이다. 각 수는 모든 행에서 정확히 한 번, 모든 열에서도 정확히 한 번 나타나야 한다(즉, 라틴 방진이다).

또한 서로 이웃한 몇몇 칸 쌍에 대해서는 둘 중 어느 칸에 더 큰 수가 들어가야 하는지가 주어진다. 미리 채워진 칸들과 이 대소 관계 조건을 모두 만족하도록 격자를 완성하여라.

첫 번째 줄에 정수 $N$ 이 주어진다 ($1 \le N < 10$).

다음 $2N - 1$ 개의 줄에는 각각 정확히 $2N - 1$ 개의 문자가 있으며 초기 상태를 나타낸다. 0부터 시작하는 인덱스로, 격자의 칸 $(r, c)$ 는 $2r$ 번째 줄의 $2c$ 번째 위치에 있다.

• 짝수 번째 줄($0, 2, 4, \ldots$)에서 짝수 번째 위치는 격자의 칸을 나타낸다. 이미 채워진 칸이면 숫자 1–9, 비어 있으면 . 이다. 홀수 번째 위치는 좌우로 인접한 두 칸 사이의 가로 방향 대소 기호로 <, >, 또는 조건이 없으면 . 이다.
• 홀수 번째 줄($1, 3, \ldots$)에서 짝수 번째 위치는 위아래로 인접한 두 칸 사이의 세로 방향 대소 기호로 ^, V, 또는 조건이 없으면 . 이다. 홀수 번째 위치는 항상 . 이다.

각 기호는 더 큰 수 쪽으로 벌어지는 부등호이다. < 는 왼쪽 칸이 오른쪽 칸보다 작음을, > 는 왼쪽 칸이 더 큼을, ^ 는 위쪽 칸이 아래쪽 칸보다 작음을, V 는 위쪽 칸이 더 큼을 뜻한다.

적어도 하나의 유효한 배치가 존재함이 보장된다. 완성된 격자를 $N$ 개의 줄로 출력하되, 각 줄에는 $N$ 개의 정수를 공백 하나로 구분하여 출력한다.

유효한 배치가 여러 개라면 사전순으로 가장 작은 것을 출력한다. 여기서 완성된 격자는 칸을 위에서 아래로, 각 행 안에서는 왼쪽에서 오른쪽으로 읽어 얻은 수열로 비교한다.