bemo

// Mugurel Ionut Andreica
// O(M * N * log(M + N))
// FARA citire parsata.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NMAX 2011

int A[NMAX][NMAX], row[NMAX * NMAX], col[NMAX * NMAX];
int M, N;

void ReadInput() {
    int i, j;

    freopen("bemo.in", "r", stdin);
    scanf("%d %d", &M, &N);
    for (i = 1; i <= M; i++)
        for (j = 1; j <= N; j++) {
            scanf("%d", &A[i][j]);
            row[A[i][j]] = i;
            col[A[i][j]] = j;
        }
}

char selected[NMAX * NMAX];
int elems[2 * NMAX], nelems;

void Solve() {
    int i, j, li, ls, mid, before;

    memset(selected, 0, sizeof(selected));
    selected[A[1][1]] = 1;
    nelems = 1;
    elems[1] = A[1][1];

    if (M == 1 && N == 1)
        return;

    selected[A[M][N]] = 1;
    nelems++;
    elems[nelems] = A[M][N];

    for (i = 1; i <= M * N && nelems < M + N - 1; i++) {
        if (selected[i])
            continue;

        // Check if we can add i to the path.
        li = 1; ls = nelems; before = 0;

        while (li <= ls) {
            mid = (li + ls) / 2;
            if (row[elems[mid]] <= row[i] && col[elems[mid]] <= col[i]) {
                before = mid;
                li = mid + 1;
            } else
                ls = mid - 1;
        }

        if (before == 0)
            continue;

        if (row[i] <= row[elems[before + 1]] && col[i] <= col[elems[before + 1]]) {
            // Insert i on position before + 1.
            for (j = nelems; j > before; j--)
                elems[j + 1] = elems[j];
            elems[before + 1] = i;
            nelems++;
            selected[i] = 1;
        }
    }

    if (nelems != M + N - 1) {
        fprintf(stderr, "Not eneough elements selected!\n");
        exit(1);
    }
}

void WriteOutput() {
    int i;

    freopen("bemo.out", "w", stdout);
    for (i = 1; i <= nelems; i++) {
        printf("%d", elems[i]);
        if (i < nelems)
            printf(" ");
    }
    printf("\n");
}

int main() {
    ReadInput();
    Solve();
    WriteOutput();
    return 0;
}