맨해튼에서의 모임

많은 동아리가 그렇듯 고려대학교 사이버국방학과 동아리 MatKor는 주기적으로 모여 활동한다. 학기 중에는 학교에서 모이는 것이 합리적이지만, 방학에는 그렇지 않다.

그래서 어떻게 모이는 것이 합리적일지 고민하던 동우는 부원들의 집을 점으로 보고 페르마 포인트에서 만나기로 했다.

페르마 포인트는 주어진 모든 점까지 거리의 합이 최소가 되는 지점이다.

동우는 택시 타기를 좋아해서 페르마 포인트를 구할 때 택시거리, 즉 맨해튼 거리를 쓰기로 했다.

위치 외에도 여러 요인을 고려하려고 집의 좌표를 N차원으로 생각하기로 했다.

점 $A$의 좌표를 $(A_1, A_2, \cdots, A_N)$, 점 $B$의 좌표를 $(B_1, B_2, \cdots, B_N)$이라 하면, 두 점의 맨해튼 거리 $d_{AB}$는 다음과 같이 정의된다.

$d_{AB} = \sum_{i=1}^N \lvert A_i - B_i\rvert = \lvert A_1 - B_1\rvert + \lvert A_2 - B_2\rvert + \cdots + \lvert A_N - B_N\rvert$

동우는 부원 $M$명의 집을 조사해 서로 다른 N차원 좌표 점 $M$개를 얻었다. 이 점들까지의 맨해튼 거리의 합이 최소가 되는 맨해튼-페르마 포인트 $F = (F_1, F_2, \cdots, F_N)$을 찾아보자.

첫 번째 줄에 점의 차원 $N$과 점의 개수 $M$이 공백으로 구분되어 주어진다 ($1 \le N, M \le 1\,000$).

다음 $M$개의 줄에는 $i$번째 점의 좌표 $P_i = (P_{i,1}, P_{i,2}, \cdots, P_{i,N})$를 나타내는 정수 $N$개가 공백으로 구분되어 주어진다 ($-10^{12} \le P_{i,j} \le 10^{12}$).

첫 번째 줄에 맨해튼-페르마 포인트를 찾아, 그 점에서 각 점까지 맨해튼 거리의 총합을 출력한다.

두 번째 줄에 맨해튼-페르마 포인트의 좌표 $F = (F_1, F_2, \cdots, F_N)$를 공백으로 구분하여 출력한다.

맨해튼-페르마 포인트의 좌표는 모두 절댓값이 $10^{12}$ 이하인 정수여야 한다. 조건을 만족하는 점이 여러 개이면 아무거나 출력한다.

주어지는 입력에 대해 조건을 만족하는 맨해튼-페르마 포인트가 존재함이 보장된다.