스키

Johan은 스키 타기를 좋아한다. 여기서 Johan이 매우 무서워하는 슬라롬을 타는 것을 말하는 것은 아니다. 그 대신 크로스컨트리 스키야말로 그가 좋아하는 것이다. 하지만 크로스컨트리 스키를 타려면 넓고 평평한 지면이 필요하다.

Johan은 숲속에 있는 지면이 상당히 고르지 않은 커다란 직사각형 영역을 조사했다. Johan은 이곳에서 스키를 재미있게 탈 수 있을 만큼 충분히 큰 특정 정사각형을 골라 그 안을 돌아다니려고 한다. 정사각형의 크기는 정확히 $L \times L$이어야 하며, 그 변은 영역의 변과 평행해야 한다.

이제 그는 그러한 정사각형을 찾아 달라고 한다. 크로스컨트리 스키를 타기에 적합하려면 두 가지 조건을 만족해야 한다. 정사각형 안에는 나무가 하나도 없어야 하며, 이 정사각형 안에서 가장 높은 지점과 가장 낮은 지점의 높이 차이가 가능한 한 작아야 한다.

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

채점

제출한 풀이는 여러 테스트 케이스 그룹으로 테스트된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

1 | 21 | $0 \leq H_{rc} \leq 1$

2 | 36 | $R,C \leq 50$

3 | 27 | $R,C \leq 300$

4 | 16 | $R,C \leq 1000$

첫째 줄에는 $1\leq R,C \leq 1000, 1 \leq L \leq min(R,C)$을 만족하는 세 정수 $R$, $C$, $L$가 주어진다. $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$이다.

해답이 존재함이 보장된다.