Sequence Center

Time limit3sMemory limit256 MB

Summary

Given k integer sequences of length n, find an integer sequence that minimizes the maximum Manhattan distance to them.

Level: Hard9 of 10
Topics: Math, Binary search
Solved: No attempts yet

Problem

You are given $k$ integer sequences of length $n$ . The distance between sequences $A=(a_1,\ldots,a_n)$ and $B=(b_1,\ldots,b_n)$ is $d(A,B)=\sum_{i=1}^{n}|a_i-b_i|$ . Find an integer sequence $C$ that minimizes $\max_i d(A_i,C)$ over the given sequences. Any optimal sequence is accepted.

Input

The first line contains $n$ and $k$ ( $2\le n\le 100000$ , $2\le k\le 5$ ). Each of the next $k$ lines has $n$ integers, the absolute values are at most $10^9$ .

Output

Print the $n$ integers of a center sequence separated by single spaces.

Examples3

Example 1

Input

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

Expected output

1 2 2 1 2

Example 2
Input
```
2 2
0 0
10 10
```
Expected output
```
0 0
```
Example 3
Input
```
3 2
1 2 3
4 5 6
```
Expected output
```
1 2 3
```