스키

Johan은 스키를 좋아한다. 물론 Johan이 무서워하는 슬라럼은 아니다. 크로스컨트리 스키야말로 그의 취미다. 하지만 크로스컨트리 스키를 타려면 넓고 평평한 면이 필요하다.

Johan은 숲속의 넓은 직사각형 지역을 조사했는데, 지형이 꽤 울퉁불퉁하다. 그는 이곳에서 스키를 타기에 충분히 큰 정사각형 하나를 골라 그 안을 돌아다니고 싶어 한다. 정사각형은 정확히 $L \times L$ 크기여야 하며, 변은 지역의 변과 평행해야 한다.

이제 그는 당신에게 그런 정사각형을 찾아 달라고 부탁한다. 크로스컨트리 스키에 잘 맞으려면 두 가지 조건이 있다. 첫째, 정사각형 안에 나무가 없어야 하고, 둘째, 이 정사각형 안에서 가장 높은 지점과 가장 낮은 지점의 높이 차가 최소여야 한다.

그런 정사각형이 여러 개라면 우선 가장 북쪽에 있는 것, 즉 행 번호가 가장 작은 것을 고른다. 그래도 여러 개라면 다음으로 가장 서쪽에 있는 것, 즉 열 번호가 가장 작은 것을 고른다.

첫째 줄에는 세 정수 $R$, $C$, $L$이 주어진다. $1\leq R,C \leq 1000$, $1 \leq L \leq min(R,C)$이다. $R$은 넓은 지역의 행 수, $C$는 열 수, $L$은 찾으려는 정사각형의 한 변의 길이이다.

그다음 $R$개의 줄이 이어지며, 지역의 각 행에 해당한다. 한 줄에는 $C$개의 정수가 주어지며, 지역의 각 열에 해당한다.

$r$번째 줄의 $c$번째 수는 지역에서 그 지점의 높이 $H_{rc}$를 나타내며, $-1 \leq H_{rc} \leq 10^9$이다. $H_{rc} = -1$이면 그 자리에 나무가 서 있다는 뜻이다.

Johan의 정사각형이 좌표 $r_l \leq r < r_l + L$, $c_l \leq c < c_l + L$을 덮는 $r_l$, $c_l$을 구한다. $r_l$과 $c_l$은 0부터 시작하는 인덱스이다. 예를 들어 첫 번째 줄(가장 북쪽)을 가리키면 $r_l = 0$이고, 첫 번째 열(가장 서쪽)을 가리키면 $c_l = 0$이다.

해가 존재하는 경우만 주어진다.