2차원

시간 제한1초메모리 제한512 MB

요약

1부터 N^2까지를 N×N 격자에 배치해 같은 행이나 같은 열에 있는 두 값의 비 p/q 중 최솟값을 최대로 만든다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 수학, 구현
정답자: 아직 제출이 없습니다

문제

다음 조건 1, 2를 만족하는 2차원 배열 $\begin{bmatrix} a\_{11} & \cdots & a\_{1N} \\\ \vdots & \ddots & \vdots \\\ a\_{N1} & \cdots & a\_{NN} \end{bmatrix}$ 중 하나를 구하는 프로그램을 작성하세요.

조건 1: $\[a\_{11}, \cdots, a\_{1N}, \cdots, a\_{N1}, \cdots, a\_{NN}]$ 은 $\[1, 2, \cdots, N^2]$ 의 순열입니다.
조건 2: 같은 행이나 같은 열에 있는 서로 다른 두 값 $p$ , $q$ ( $p > q$ )에 대한 $\frac{p}{q}$ 들의 최솟값을 배열의 점수라고 할 때, 점수가 최대입니다.

입력

첫 번째 줄에 양의 정수 $N$ 이 주어집니다.

출력

$i$ ( $1 \le i \le N$ )번째 줄에 문제의 조건을 만족하는 $a\_{i1}, a\_{i2}, \ldots, a\_{iN}$ 을 출력합니다.

제한

$2 \le N \le 2 \times 10^3$

예제1

예제 1
입력
```
2
```
예상 출력
```
1 3
4 2
```