다트

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N×N 점수판과 정확도 L이 주어질 때, 주변 (2L+1)×(2L+1) 영역에 있는 칸들의 평균 점수가 가장 높은 칸의 좌표를 구합니다.

난이도: 보통10점 중 4점
유형: 누적 합, 행렬
정답자: 아직 제출이 없습니다

문제

아도마스가 다시 다트를 던진다. 벽에 정사각형 과녁이 걸려 있고, 과녁은 $1 \times 1$ 크기의 칸으로 나뉘어 있다. 각 칸에는 그 칸을 맞혔을 때 얻는 정수 점수가 적혀 있다. 과녁을 빗나가면 0점이다. 각 칸은 좌표 $(X, Y)$ 를 가지며, $X$ 는 과녁 왼쪽 가장자리로부터의 칸 수, $Y$ 는 위쪽 가장자리로부터의 칸 수이다. 왼쪽 위 칸은 $(1, 1)$ , 오른쪽 아래 칸은 $(N, N)$ 이다.

아도마스는 그리 정확하지 않다. 칸 $(X, Y)$ 를 노리면, $|X - X'| \le L$ 이고 $|Y - Y'| \le L$ 인 어떤 칸 $(X', Y')$ 에든 같은 확률로 맞을 수 있다.

아도마스의 정확도가 $L = 1$ 이고 그림의 과녁을 쓴다면, 아도마스는 $(3, 2)$ 칸을 노려야 한다. 그러면 그림의 초록색 칸 중 어디든 맞힐 수 있고, 평균 점수는 $7/3$ 이다.

그림 1.

아도마스가 평균 점수를 가장 높게 얻으려면 어느 칸을 노려야 하는지 구하시오.

입력

첫 줄에 과녁의 한 변 길이 $N$ 과 노린 칸에서 맞힌 칸까지의 최대 거리 $L$ 이 주어진다. 이어서 $N$ 개의 줄에 각각 $N$ 개의 정수 $T(X, Y)$ 가 주어지며, 이는 칸 $(X, Y)$ 에 적힌 점수이다.

출력

아도마스가 노려야 할 칸의 좌표 $X$ 와 $Y$ 를 정수 두 개로 출력한다. 답이 여러 개이면 그중 아무거나 출력해도 된다.

제한

$1 \le N \le 1000$
$0 \le L, T(X, Y) \le 1000$

예제3

예제 1
입력
```
3 1
1 2 3
4 5 6
7 8 9
```
예상 출력
```
2 2
```

예제 2

입력

예상 출력

3 2

예제 3
입력
```
2 0
7 101
999 4
```
예상 출력
```
1 2
```