the-smallest-path-1-92

Maga gives a hard problem to Alex. And Alex couldn't solve yet. Could you help him?

The grid is n by m. Each cell contains a unique number on it. Maga is at the left-top and wants to go to right-bottom. But there is a condition. Maga can go through only two way - right and down. And the path of your move is called the nodes you have passed through over them. The path is called the most beautiful if the following condition is satisfied: The sorted of the path has to be lexicographic smallest as possible as. Output the most beautiful path for given grid.

Input:
In the first line you are given two numbers: the dimensions of grid - n and m.
The next n lines contains m numbers. Each number is unique.

Output:
Output the most beautiful path.

Contraints:
1 ≤ n,m ≤ 1000
1 ≤ A[i][j] ≤ n*m, All of the numbers in the grid are unique.

SAMPLE INPUT
2 2
4 2
3 1

SAMPLE OUTPUT
1 2 4

Explanation

There are 2 ways to reach at (2,2) cell. The pathes are 4, 3, 1 or 4, 2, 1 respectively. So The most beautiful of them is 4, 2, 1 because if looking the sorted of them it looks like these : 1, 3, 4 and 1, 2, 4 respectively. So 1, 2, 4 is lexicographic smaller than the other. So the ans is 1 2 4.

Source: hackerearth | Difficulty: HARD


Solutions: