1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <utility>
#include <vector>

#define REP(a, n) for (int a = 0; a < (n); ++a)
#define FOR(a, b, c) for (int a = (b); a <= (c); ++a)
#define FORD(a, b, c) for (int a = (b); a >= (c); --a)

typedef long long LL;

using namespace std;

template<class T> inline int vsize(const T &t) { return t.size(); }

/////////////////

int YS, XS, Q;

vector<vector<LL>> F;
vector<vector<LL>> wyn;
vector<vector<LL>> tab;
vector<vector<LL>> tmp;
vector<LL> kor;

inline LL FF(int y0, int y1) {
    return F[y0][y1-y0];
}

void wypF() {
    REP(y0, YS)
        FOR(y1, y0, YS-1)
            fprintf(stderr, "f(%d,%d)=%lld\n", y0, y1, FF(y0, y1));
}

int main() {
    scanf("%d%d%d", &YS, &XS, &Q);
    tab.resize(YS);
    tmp.resize(YS);
    F.resize(YS);
    kor.resize(YS);
    wyn.resize(YS);
    REP(y, YS) {
        tmp[y].resize(XS);
        REP(x, XS) {
            int a;
            scanf("%d", &a);
            tab[y].push_back(a);
        }
    }
    REP(yc, YS) {
        REP(yy, yc+1)
            tmp[yy][XS-1] = tab[yc][XS-1];
        FORD(x, XS-2, 1) {
            tmp[yc][x] = tmp[yc][x+1] + tab[yc][x];
            FORD(yy, yc-1, 0) 
                tmp[yy][x] = min(tmp[yy][x+1] + tab[yy][x], tmp[yy+1][x]);
        }
        REP(yy, yc+1)
            F[yy].push_back(tmp[yy][1]+tab[yy][0]);
//        fprintf(stderr,"DO %d: \n", yc); REP(y, yc+1) {fprintf(stderr, "%d+ ", tab[y][0]); REP(x, XS) fprintf(stderr, "%lld%c", tmp[y][x], x==XS-1?'\n':' ');}
    }
//    wypF();
    REP(y0, YS) {
        kor[y0] = FF(y0, YS-1);
        for (LL &p : F[y0]) p -= kor[y0];
    }
    REP(y1, YS)
        wyn[y1].push_back(FF(0, y1));
    FOR(y0, 1, YS-1) {
        int y1 = YS-1;
        while (y1>y0 && FF(y0, y1-1)==FF(y0-1, y1-1)) --y1;
        y1--;
//        fprintf(stderr, "dla %d zaczynam na %d\n", y0, y1);
        while (y1>=y0) {
            while (vsize(wyn[y1])+1>vsize(wyn[y1+1]))
                wyn[y1+1].push_back(0);
            wyn[y1].push_back(FF(y0, y1)-FF(y0-1, y1));
//            fprintf(stderr, "wstawiam %lld-%lld\n", FF(y0, y1), FF(y0-1, y1));
            y1--;
        }
    }
    ///////////////// jesli szerszy, to wypisz oryginalny
    
    
    int ss = 0;
    REP(y, YS) ss = max(ss, vsize(wyn[y]));
    if (ss>XS) {
        REP(y, YS) {
            swap(wyn[y], tab[y]);
            reverse(wyn[y].begin(), wyn[y].end());
        }
    }
    else {
        REP(y, YS) wyn[y].resize(ss);
        REP(y, YS) wyn[y].push_back(kor[y]);
    }
    printf("%d\n", vsize(wyn[0]));
    if (Q)
        REP(y, YS)
            FORD(x, vsize(wyn[0])-1, 0)
                printf("%lld%c", wyn[y][x], x ? ' ' : '\n');
}