Minimizing the Maximum L1 Distance over Sequences

You are given k sequences each of length n: \(A_1,A_2,\cdots,A_k\). The distance between two sequences \(a\) and \(b\) (both of length \(n\)) is defined as

[ \operatorname{dist}(a,b)=\sum_{i=1}^{n} |a_i-b_i| ]

Your task is to construct a sequence \(B\) of length \(n\) such that the value

[ F(B)=\max_{1\le i\le k} \operatorname{dist}(A_i,B) ]

is minimized. In other words, you want to choose (B) so that the worst-case (L_1) distance to any of the given sequences is as small as possible.

Hint: The problem can be solved coordinate by coordinate. For each position \(j\) (where \(1 \le j \le n\)), let

[ L_j=\min_{1\le i \le k} A_i[j] \quad \text{and} \quad R_j=\max_{1\le i \le k} A_i[j]. ]

The optimal choice at the (j)-th coordinate is

[ B[j]=\frac{L_j+R_j}{2}, ]

which minimizes the maximum absolute difference (|A_i[j]-B[j]|) over all sequences.

inputFormat

The first line contains two integers n and k (n is the length of each sequence and k is the number of sequences).

Then follow k lines, each containing n numbers which represent the sequence \(A_i\). The numbers can be integers or decimals.

outputFormat

Output one line containing n numbers separated by a space, representing the sequence \(B\) that minimizes \(\max_{1\le i\le k} \operatorname{dist}(A_i,B)\). The numbers should be output in decimal format if necessary.

sample

3 2
1 2 3
3 2 1

2 2 2