Lexicographically Smallest Addition Table Restoration

Bessie has an \(N \times N\) addition table where for every \(1\leq r,c\leq N\), the integer in the cell at row \(r\) and column \(c\) is \(r+c\). For example, when \(N=3\), the table is:

2 3 4
3 4 5
4 5 6

Unfortunately, Elsie obtained this table and performed a sequence of operations on it. The operations are executed in three phases in the following fixed order:

1. Swap any two rows any number of times.
2. Swap any two columns any number of times.
3. Select two values \(a\) and \(b\) that both appear in the table, and swap every occurrence of \(a\) with \(b\) simultaneously.

Your task is to help Bessie recover one possible state of the table after all the type 1 and type 2 operations (row and column swaps) have been performed but before any type 3 operations (value swap) are executed. If multiple table states are possible, output the lexicographically smallest table. The lexicographical order is defined by comparing the table entries in natural reading order (row by row, from left to right) and choosing the table with the smallest first differing element.

Note: The lexicographically smallest state is achieved by simply keeping the rows and columns in increasing order.

inputFormat

The input consists of a single integer \(N\) (\(1 \leq N \leq 1000\)), representing the size of the table.

outputFormat

Output the \(N\) lines, each containing \(N\) space-separated integers, representing the lexicographically smallest state of the table after the row and column swaps.

sample

1

2