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 <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const ll inf = 1e12 + 5;

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n, m, q;
   cin >> n >> m >> q;
  
   vector<vector<int>> v(n, vector<int>(m, 0));
   for(auto &a : v) {
      for(auto &x : a) cin >> x;
   }
   
   vector<int> templ;
   
   if(n <= m) {   
      for(int i = 0; i < n; i++) {
      vector<vector<ll>> dp(n, vector<ll>(m, 0));
         for(int j = i + 1; j < n; j++)
            dp[j][0] = inf;
         dp[i][0] = v[i][0];
         
         for(int col = 1; col < m; col++) {
            ll mn = inf;
            for(int linie = i; linie < n; linie++) {
               mn = min(mn, dp[linie][col - 1]);
               dp[linie][col] = v[linie][col] + mn;
            }
         }
         
         vector<int> mine(n);
         for(int j = i; j < n; j++) mine[j] = dp[j][m - 1];
         
         if(i == 0) {
            templ = mine;
         }
         else {
            for(int j = i + 1; j < n; j++) {
               if(mine[j] - templ[j] != mine[i] - templ[i]) {
                  cout << "3\n";
                  return 0;
               }
            }
         }
      }
      
      cout << "2\n";
   }
   
   else {
      vector<ll> pref_max(m, -inf);
      vector<ll> pref_min(m, inf);
      pref_max[m - 1] = 0;
      pref_min[m - 1] = 0;
      for(int i = n - 1; i >= 0; i--) {
         
         vector<ll> mxp = pref_max;
         vector<ll> mnp = pref_min;
         
         pref_max.assign(m, inf);
         pref_min.assign(m, inf);
         
         
         for(int r = m - 2; r > 0; r--) {
            
            ll sum = 0;
            for(int l = r; l > 0; l--) {
               sum += v[i][l];
               pref_max[l] = max(mxp[r + 1] + sum, pref_max[l]);
               pref_min[l] = min(mnp[r + 1] + sum, pref_min[l]);
            }
            if(r == m - 2 && sum != 0) {
               cout << "3\n";
               return 0;
            }
         }
         
         if(pref_min[1] < 0) {
            cout << "3\n";
            return 0;
         }
      }
      cout << "2\n";
      return 0;
   }
   
}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/