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
#include <climits>
#include <cstdio>
#include <cstdlib>

int k, n, A[5][100000], B[5];

long long oblicz(int a) {
	long long s = 0;
	for (int i = 0; i < k; ++i) s += abs(B[i] - a);
	return s;
}

int znajdz(int a, int b) {
	int c, d, e;
	long long x, y;
	c = (a + b) / 2;
	while (b - a > 2) {
		d = (a + c) / 2;
		x = oblicz(d);
		e = (c + b) / 2;
		y = oblicz(e);
		if (x < y) {
			b = c;
			c = d;
		} else {
			a = c;
			c = e;
		}
	}
	x = LLONG_MAX;
	c = 0;
	for (int i = a; i <= b; ++i) {
		y = oblicz(i);
		if (y < x) {
			x = y;
			c = i;
		}
	}
	return c;
}

int main() {
	int a, b;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < k; ++i) {
		for (int j = 0; j < n; ++j) scanf("%d", &A[i][j]);
	}
	for (int i = 0; i < n; ++i) {
		a = 1000000001;
		b = -a;
		for (int j = 0; j < k; ++j) {
			B[j] = A[j][i];
			if (B[j] < a) a = B[j];
			if (B[j] > b) b = B[j];
		}
		printf("%d ", znajdz(a, b));
	}
	puts("");
	return 0;
}