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<cstdio>
#include<algorithm>
#include<vector>

using namespace std;
typedef long long ll;
ll inf = 1e16;
vector<vector<int>> T;
vector<vector<ll>> dp;
vector<vector<ll>> dp2;

int main(void){
    int n,m,q;
    scanf("%d %d %d",&n,&m,&q);
    ll d = max(n,m);
    T.resize(n+7);
    dp.resize(n+7);
    dp2.resize(n+7);
    for(int i = 0; i <= n+1; i++){
        T[i].resize(m+7);
        dp[i].resize(m+7);
        dp2[i].resize(n+7);
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int x;
            scanf("%d", &T[i][j]);
        }
    }
    
    for(int d = n; d >= 1; d--){
        for(int i = 1; i <= n; i++){
            dp[i][m] = inf;
        }
        dp[d][m] = T[d][m];
        for(int i = n; i >= 1; i--){
            for(int j = m; j >= 2; j--){
                dp[i][j] = inf;
                if(j == m && i == d){
                    dp[i][j] = T[i][j];
                    continue;
                }
                ll p = inf;
                if(j != m){
                    p = min(p, T[i][j] + dp[i][j+1]);
                }
                if(i != n){
                    p = min(p, dp[i+1][j]);
                }
                dp[i][j] = min(dp[i][j], p);
            }
        }
        for(int i = 1; i <= n; i++){
            dp2[i][d] = dp[i][2] + T[i][1];
        }
    }
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= n; j++){
    //         printf("%d %d %lld\n",i,j,dp2[i][j]);
    //     }
    // }
    vector<ll> A(n+7);
    vector<ll> B(n+7);
    A[1] = 0;
    for(int i = 1; i <= n; i++){
        B[i] = dp2[1][i];
    }
    for(int i = 2; i <= n; i++){
        A[i] = dp2[i][n] - B[n];
    }

    bool two = true;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            if(A[i] + B[j] != dp2[i][j])
                two = false;
        }
    }

    if(two){
        printf("2\n");
        if(q == 1){
            for(int i = 1; i <= n; i++){
                printf("%lld %lld\n",A[i], B[i]);
            }
        }
    }else{
        printf("3\n");
        if(q == 1){
            for(int i = 1; i <= n; i++){
                printf("%lld 0 %lld\n",A[i], B[i]);
            }
        }
    }

    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= n; j++){
    //         printf("%d %d %lld*\n",i,j,dp2[i][j]);
    //     }
    // }

    return 0;
}