Problem description

Jasio ma zamiar przejść kratownicę o wymiarach N × M idąc z lewego górnego rogu do prawego dolnego wykonując tylko ruchy w dół i w prawo. Na każdym polu kratownicy znajduje się liczba naturalna. Liczby na polach kratownicy są parami różne. Jasio chciałby, aby jego przejście kratownicy dawało ścieżkę, dla której odczytanie kolejnych pól kratownicy utworzy ciąg możliwie najmniejszy leksykograficznie. Pomóż mu!

Napisz program, który: wczyta opis kratownicy, wyznaczy najmniejszy leksykograficznie napis, który można uzyskać przechodząc (zgodnie z ustalonymi zasadami Jasia) ścieżką z lewego górnego wierzchołka do prawego dolnego wierzchołka i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz M, oddzielone pojedynczym odstępem i określające kolejno: wysokość i szerokość kratownicy. W kolejnych N wierszach znajduje się opis kratownicy – po M liczb naturalnych A_i, j, pooddzielanych pojedynczymi odstępami na wiersz.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia należy wypisać liczby na optymalnej ścieżce dla podanej na wejściu kratownicy. Liczby mają być wypisane w kolejności zgodnej ze kolejnością pól na ścieżce i pooddzielane pojedynczymi odstępami.

Ograniczenia

1 ≤ N, M ≤ 1 000, 1 ≤ A_i, j ≤ 10⁹.

Przykład

3 3
4 7 6
8 3 9
5 1 2

4 7 3 1 2 

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

1 2 4 6 8 10 

4 4
3 9 2 16
5 1 4 15
14 10 6 8
11 7 12 13

3 5 1 4 6 8 13