수열 중심

시간 제한3초메모리 제한256 MB

요약

길이 n인 정수 수열 k개가 주어질 때 모든 수열까지의 맨해튼 거리 중 최댓값을 가장 작게 만드는 정수 수열을 구합니다.

난이도: 어려움10점 중 9점
유형: 수학, 이분 탐색
정답자: 아직 제출이 없습니다

문제

길이 $n$ 인 정수 수열 $k$ 개가 주어진다. 두 수열 $A=(a_1,\ldots,a_n)$ , $B=(b_1,\ldots,b_n)$ 사이의 거리는 $d(A,B)=\sum_{i=1}^{n}|a_i-b_i|$ 로 정의한다. $k$ 개 수열 $A_1,\ldots,A_k$ 에 대해 $\max_i d(A_i,C)$ 를 최소화하는 정수 수열 $C$ 를 하나 출력한다. 여러 답이 있으면 아무거나 출력해도 된다.

입력

첫 줄에 $n$ , $k$ ( $2\le n\le 100000$ , $2\le k\le 5$ )가 주어진다. 다음 $k$ 줄에 각 수열의 $n$ 개 정수가 주어진다. 절댓값은 $10^9$ 이하이다.

출력

중심 수열 $C$ 의 $n$ 개 정수를 공백으로 구분해 한 줄에 출력한다.

예제3

예제 1

입력

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

예상 출력

1 2 2 1 2

예제 2
입력
```
2 2
0 0
10 10
```
예상 출력
```
0 0
```
예제 3
입력
```
3 2
1 2 3
4 5 6
```
예상 출력
```
1 2 3
```