27297번 - 맨해튼에서의 모임 스페셜 저지

많은 동아리가 그렇듯 고려대학교 사이버국방학과 동아리 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})$ ($-10^{12} \le P_{i,j} \le 10^{12}$)를 나타내는 $N$개의 정수가 공백으로 구분되어 주어진다.

첫 번째 줄에 주어진 점들로부터의 맨해튼-페르마 포인트을 찾아 그 점에서부터 각 점까지 맨해튼 거리의 총합을 출력한다.

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

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

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