#P11814. [PA 2014] 串串 / Ciągi

[PA 2014] 串串 / Ciągi

题目背景

译自 PA 2014 R5。

题目描述

给定 kk 个长度为 nn 的序列 A1,A2,,AkA_1,A_2,\cdots,A_k

定义两个长度为 nn 的序列 a,ba,b距离 dist(a,b)\operatorname{dist}(a,b) 为:

$$\operatorname{dist}(a,b)=\sum_{1\le i\le n} |a_i-b_i| $$

你需要构造一个长度为 nn 的序列 BB,最小化 $\displaystyle \max_{1\le i\le k} \operatorname{dist}(A_i,B)$ 的值。

输入格式

第一行,两个正整数 n,kn,k

接下来 kk 行,第 iinn 个整数 Ai,1,Ai,2,,Ai,nA_{i,1},A_{i,2},\cdots,A_{i,n}

输出格式

输出 nn 个整数,表示你构造的 BB 序列。

你需要保证你输出的数在 [231,231)[-2^{31},2^{31}) 内。

5 3
1 -1 2 -1 2
1 2 2 1 2
2 2 -1 1 1
1 2 2 1 2

提示

  • 2n1052\le n\le 10^5
  • 2k52\le k\le 5
  • Ai,j109|A_{i,j}|\le 10^9