Problem description

Dana jest macierz wymiaru N × M wypełniona parami różnymi liczbami naturalnymi od 1 do N × M (każda liczba z tego przedziału występuje w macierzy dokładnie raz).

Należy wyznaczyć najlżejszą ścieżkę z lewego górnego pola macierzy do prawego dolnego pola macierzy. Ścieżka, jak to zwykle w takich zadaniach bywa, może biec tylko w dół lub w prawo. Nietypowe jest jednak to jak porównujemy ścieżki.

Ścieżka A jest lżejsza od innej ścieżki B, jeśli po posortowaniu wszystkich wyrazów macierzy występujących na obu ścieżkach, otrzymany ciąg dla ścieżki A będzie mniejszy leksykograficznie od ciągu otrzymanego dla ścieżki B.

Napisz program, który: wczyta opis macierzy, wyznaczy optymalną (najlżejszą) ścieżkę zgodnie z powyższymi warunkami i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, oddzielone pojedynczym odstępem i określające kolejno: wysokość i szerokość macierzy. W kolejnych N wierszach znajduje się opis kolejnych wierszy macierzy – ciąg M liczb naturalnych T_i, j pooddzielanych pojedynczymi odstępami.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinien się znaleźć ciąg liczb pooddzielanych pojedynczymi odstępami – kolejne wyrazy macierzy leżące na optymalnej ścieżce w zadanej macierzy.

Ograniczenia

1 ≤ N, M ≤ 1 000, 1 ≤ T_i, j ≤ N ⋅ M.

Przykład

3 4
8 2 3 4
10 1 5 6
12 11 7 9

8 2 1 5 6 9