Maze Path with Balanced Climbs

BaoBao the Witch is stuck in a maze with n rows and n columns. The height of the cell in the i-th row and j-th column is \(h_{i,j}\). All the cell heights form a permutation of \(1,2,\dots,n^2\). In order to escape, BaoBao must find a Hamiltonian path that visits each cell exactly once, moving only to adjacent (edge‐sharing) cells.

However, whenever she climbs up (i.e. moves from a cell with a smaller height to a cell with a larger height), her happiness decreases. Your task is to output a valid path such that the total number of "climbing up" moves is not more than the number of "climbing down" moves.

More formally, you need to find a sequence of cells \((x_1,y_1), (x_2,y_2), \dots, (x_{n^2}, y_{n^2})\) such that:

• \(1 \le x_i, y_i \le n\) for all \(1 \le i \le n^2\);
• All cells are distinct;
• For every \(2 \le i \le n^2\), \(|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1\) (adjacent moves);
• \(\sum_{i=2}^{n^2} [h_{x_{i-1},y_{i-1}} h_{x_i,y_i}]\), where \([P]=1\) if \(P\) is true and \(0\) otherwise.

You only need to output the heights of the cells in the order they are visited along your valid path.

Note: A simple snake (zigzag) traversal is allowed, but if the number of climbs is more than the number of descents, you may output the reverse of the snake path. This always guarantees that the number of upward moves is not more than the downward moves.

inputFormat

The first line contains a single integer n (the maze has n rows and n columns). Following this, there are n lines, each containing n integers. The j-th number on the i-th line represents h_i,j.

outputFormat

Output a single line with n² integers, representing the heights of the cells along a valid path. The integers should be separated by single spaces.

sample

2
1 2
3 4

3 4 2 1