/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
N \times N のマス目があります。上から i 行目、左から j 列目のマスを (i,j) で表します。
以下の条件を満たすように各マスに非負整数を 1 つずつ書き込む方法を 1 つ出力して下さい。
右または下に隣接するマスへの移動のみを繰り返してマス (1,1) からマス (N,N) まで到達する経路について、経路上に含まれるマス（始点・終点を含む）に書かれた整数の総和を経路のスコアとする。
このとき、\binom{2N-2}{N-1} 通りある経路について、スコアは互いに異なり、全て 6 \times 10^6 以下である。
制約
- 2 \le N \le 13
入力
入力は以下の形式で標準入力から与えられる。
N
出力
問題文中の条件を満たすような書き込み方について、マス (i,j) に書き込む非負整数を A_{i,j} とし、これを以下の形式で出力せよ。
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
解が複数存在する場合は、どれを出力しても正解とみなされる。
入力例 1
2
出力例 1
1 2 3 4
右・下の順で移動する経路のスコアは 7、下・右の順で移動する経路のスコアは 8 であり、問題文中の条件を満たします。
入力例 2
5
出力例 2
10443 257776 131299 258759 153153 103533 63158 120370 132605 22808 206213 155047 237224 121264 96487 213665 51789 237311 239387 27085 229301 125534 154776 40898 210765
Score : 700 points
Problem Statement
There is an N \times N grid. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.
Output one way to write a non-negative integer in each cell so that the following condition is satisfied.
For a path from cell (1,1) to cell (N,N) by repeating moves only to adjacent cells to the right or down, let the score of the path be the sum of the integers written in the cells on the path (including the start and end points).
Then, for all \binom{2N-2}{N-1} possible paths, the scores are all distinct and all at most 6 \times 10^6.
Constraints
- 2 \le N \le 13
Input
The input is given from Standard Input in the following format:
N
Output
For a way of writing that satisfies the condition in the problem statement, let A_{i,j} be the non-negative integer written in cell (i,j), and output it in the following format:
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
If there are multiple solutions, any of them will be accepted.
Sample Input 1
2
Sample Output 1
1 2 3 4
The score of the path that moves right then down is 7, and the score of the path that moves down then right is 8, satisfying the condition in the problem statement.
Sample Input 2
5
Sample Output 2
10443 257776 131299 258759 153153 103533 63158 120370 132605 22808 206213 155047 237224 121264 96487 213665 51789 237311 239387 27085 229301 125534 154776 40898 210765