[AdditionalFile5300.zip](file://AdditionalFile5300.zip?type=additional_file)

#5300. 「PA 2014」Ciągi

标签: 传统 | 时间限制: 2000 ms | 内存限制: 128 MiB |

题目描述

题目译自 PA 2014 Runda 5 Ciągi

在本题中，我们考虑长度为 $n$ 的整数序列。两个序列 $A = (a_{1}, a_{2}, \ldots, a_{n})$ 和 $B = (b_{1}, b_{2}, \ldots, b_{n})$ 之间的距离定义为：

$$d(A, B) = |a_{1} - b_{1}| + |a_{2} - b_{2}| + \ldots + |a_{n} - b_{n}|,$$

其中 $|x|$ 表示数字 $x$ 的绝对值。

给定 $k$ 个序列 $A_{1}, A_{2}, \ldots, A_{k}$，你的任务是找到它们的中心，即一个整数序列，使得以下值：

$$\max \left\{d(A_{i}, B): i=1,2,\ldots,k\right\}$$

尽可能小。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $k$ $(2 \leq n \leq 100000, 2 \leq k \leq 5)$。

接下来的 $k$ 行，每行描述一个序列，包含 $n$ 个整数，绝对值不超过 $10^{9}$。

输出格式

输出一行，包含 $n$ 个用单个空格分隔的整数，描述输入序列的中心。如果存在多个正确答案，你的程序可以输出其中任意一个。

样例

输入

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

输出

1 2 2 1 2

数据范围与提示

对于 $10\%$ 的数据，$k \leq 2$。
对于 $30\%$ 的数据，$k \leq 3$。
对于 $60\%$ 的数据，$k \leq 4$。