In this task, we consider sequences of integers of length $n$. The distance between two such sequences $A = (a_1, a_2, \dots, a_n)$ and $B = (b_1, b_2, \dots, b_n)$ is defined as: $$d(A, B) = |a_1 - b_1| + |a_2 - b_2| + \dots + |a_n - b_n|,$$ where $|x|$ denotes the absolute value of the number $x$.

Given $k$ sequences $A_1, A_2, \dots, A_k$, your task is to find their center, i.e., a sequence of integers $B$ for which the value $$\max\{d(A_i, B) : i = 1, 2, \dots, k\}$$ is as small as possible.

Input

The first line of input contains two integers $n$ and $k$ ($2 \le n \le 100\,000$, $2 \le k \le 5$). Each of the following $k$ lines contains the description of one of the sequences as $n$ integers, each with an absolute value not exceeding $10^9$.

Subtasks

In tests worth 1 point, the condition $k \le 2$ holds. In tests worth a total of 3 points, the condition $k \le 3$ holds. In tests worth a total of 6 points, the condition $k \le 4$ holds.

Output

The only line of output should contain $n$ integers separated by single spaces, describing the center of the given sequences. If there is more than one correct answer, your program may output any of them.

Examples

Input 1

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

Output 1

1 2 2 1 2

Note

The distances of the resulting sequence from the individual input sequences are 5, 0, and 5.