题目描述

题目译自 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}$，需找到一个整数序列 $B$（称为“中心”），使得 $\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$ 个整数，描述一个序列 $A_i$，序列中元素的绝对值不超过 $10^9$。

输出格式

输出一行，包含 $n$ 个用单个空格分隔的整数，表示满足条件的中心序列 $B$。若存在多个正确答案，输出任意一个即可。

样例

输入

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$；
• 100% 的数据：$2 \leq n \leq 10^5, 2 \leq k \leq 5$，序列元素绝对值 $\leq 10^9$