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
105
106
107
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int abs(const int x) {
  return x > 0 ? x : -x;
}

int min(const long long a, const long long b) {
  return a < b ? a : b;
}

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  vector<vector<int> > v(k, vector<int>(n));
  for (int i = 0; i < k; ++i) for (int j = 0; j < n; ++j) scanf("%d", &v[i][j]);

  long long best = -1;
  long long best_i = -1;
  long long best_j = -1;
  for (int i = 0; i < k; ++i) for (int j = 0; j < i; ++j) {
    long long m = 0;
    for (int l = 0; l < n; ++l) m += abs(v[i][l] - v[j][l]);
    if (m > best) {
      best = m;
      best_i = i;
      best_j = j;
    }
  }

  // cerr << best_i << ' ' << best_j << ' ' << best << endl;

  long long total_i = 0;
  long long total_j = 0;
  vector<int> ret(n);

  for (int l = 0; l < n; ++l) {
    const long long value_min = min(v[best_i][l], v[best_j][l]);
    ret[l] = value_min;
    total_i += abs(ret[l] - v[best_i][l]);
    total_j += abs(ret[l] - v[best_j][l]);
  }

  for (int i = 0; i < k; ++i) if (i != best_i && i != best_j) {
    total_i = 0;
    total_j = 0;
    for (int l = 0; l < n; ++l) {
      long long value = v[i][l];
      const long long value_min = min(v[best_i][l], v[best_j][l]);
      const long long value_max = max(v[best_i][l], v[best_j][l]);
      if (value < value_min) value = value_min;
      if (value > value_max) value = value_max;
      ret[l] = value;
      total_i += abs(ret[l] - v[best_i][l]);
      total_j += abs(ret[l] - v[best_j][l]);
    }
  }

  for (int l = 0; l < n; ++l) {
    if (total_i > total_j) {
      long long gain = (total_i - total_j) / 2;
      if (ret[l] < v[best_i][l]) {
        gain = min(gain, v[best_i][l] - ret[l]);
        ret[l] += gain;
        total_i -= gain;
        total_j += gain;
      } else {
        gain = min(gain, ret[l] - v[best_i][l]);
        ret[l] -= gain;
        total_i -= gain;
        total_j += gain;
      }
    } else {
      long long gain = (total_j - total_i) / 2;
      if (ret[l] < v[best_j][l]) {
        gain = min(gain, v[best_j][l] - ret[l]);
        ret[l] += gain;
        total_j -= gain;
        total_i += gain;
      } else {
        gain = min(gain, ret[l] - v[best_j][l]);
        ret[l] -= gain;
        total_j -= gain;
        total_i += gain;
      }
    }
  }

  for (int i = 0; i < k; ++i) {
    long long dist = 0;
    for (int l = 0; l < n; ++l) dist += abs(ret[l] - v[i][l]);
    // cerr << dist << endl;
    assert(dist <= (best + 1) / 2);
  }

  for (int i = 0; i < n; ++i) {
    if (i != 0) printf(" ");
    printf("%d", ret[i]);
  }
  printf("\n");

  return 0;
}