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
#include <cstdio>
#include <algorithm>
using namespace std;

int c[5][100000];
int w[100000][5];
int p[100000];
long long limit[100000];
long long d[5];
pair<long long, int> l[5];
const int INF = 2000000000;
int n;

void popraw(int m1, int m2)
{
    for(int i = 0; i < n; i++)
    {
	int q = min(min(limit[i], (long long)abs(c[m1][i] - p[i])), (d[m1] - d[m2]) / 2);
	if(c[m1][i] > p[i]) p[i] += q;
	else p[i] -= q;
	d[m1] -= q;
	d[m2] += q;
    }
}

int main()
{
    int k, K;
    scanf("%d %d", &n, &k);
    K = min(3, k);
    for(int i = 0; i < K; i++)
	for(int j = 0; j < n; j++)
	{
	    scanf("%d", &c[i][j]);
	    w[j][i] = c[i][j];
	}
    for(int i = 0; i < n; i++)
    {
	limit[i] = INF;
	sort(w[i], w[i] + K);
	p[i] = w[i][1];
    }
    for(int i = 0; i < K; i++)
    {
	for(int j = 0; j < n; j++)
	    d[i] += abs(c[i][j] - p[j]);
	l[i] = make_pair(-d[i], i);
    }
    sort(l, l + K);
    int m1 = l[0].second, m2 = l[1].second, m3 = 3;
    if(k == 4)
    {
	for(int i = 0; i < n; i++)
	    if(abs(p[m1] - p[m2]) + abs(p[m3] - p[m2]) == abs(p[m1] - p[m3]))
		limit[i] = 0;
	    else if(abs(p[m1] - p[m3]) + abs(p[m2] - p[m3]) == abs(p[m1] - p[m2]))
		limit[i] = abs(p[i] - p[m3]);
    }
    popraw(m1, m2);
    if(k == 4)
    {
	for(int i = 0; i < n; i++)
	    limit[i] = INF;
	if(d[m2] > d[m3]) popraw(m1, m2);
	else if(d[m3] > d[m1]) popraw(m3, m1);
	else popraw(m1, m3);
    }
    for(int i = 0; i < n; i++)
	printf("%d ", p[i]);
    puts("");
}