그라디언트 광산 찾기

외계인의 침공 가능성에 대비하려면, 먼저 그들이 어디에서 올 수 있는지 알아내야 한다. 어떤 행성에 지적 생명체가 살고 있는지 판단하는 한 가지 방법은, 그 행성의 고해상도 사진을 분석해 지적 생명체가 남긴 특징적인 흔적을 찾는 것이다. 후보 행성이 매우 많기 때문에 이 작업은 컴퓨터 프로그램으로 수행해야 한다.

문명이 자리 잡은 행성의 두드러진 특징 중 하나는 지표면에 있는 광산이다. 광산은 정사각형 모양의 구조물로, 그 깊이가 정사각형의 한 변에서 맞은편 변으로 갈수록 일정하게 변한다. 따라서 흑백 사진에서 광산은 명암이 일정하거나, 한 방향에서 반대 방향으로 점진적이고 균일하게 변하는 정사각형으로 나타난다.

당신의 임무는 어떤 행성의 흑백 비트맵 사진에서 가장 큰 광산을 찾는 것이다. 사진은 $0$ 이상 $65535$ 이하의 정수로 이루어진 직사각형 격자이며, $A_{i,j}$ 는 $i$ 번째 행, $j$ 번째 열에 있는 픽셀의 명암(회색조)을 나타낸다. 특정한 몇 가지 방향으로 놓인 정사각형 광산만 고려한다.

변의 길이가 $L$ 인 축에 평행한 정사각형은 $r \le i \le r+L-1$ 이고 $c \le j \le c+L-1$ 인 픽셀 $A_{i,j}$ 들의 블록이다.

이러한 정사각형은, 어떤 정수 $S$ 와 $K$ 에 대해 명암이 다음 네 가지 그라디언트 패턴 중 하나를 따를 때 광산이 된다.

• 행 그라디언트(세로 광산): $A_{i,j} = S + iK$ — 명암이 행 번호에만 의존한다.
• 열 그라디언트(가로 광산): $A_{i,j} = S + jK$ — 명암이 열 번호에만 의존한다.
• 대각선 그라디언트: 어떤 $Q \in \{+1, -1\}$ 에 대해 $A_{i,j} = S + (i + Qj)K$ — 명암이 두 대각선 방향 중 하나를 따라 일정하다.

픽셀 하나짜리 정사각형은 언제나 (자명한) 광산이다.

입력에는 여러 개의 사진이 주어진다. 각 사진은 두 정수 $N$ 과 $M$ ($1 \le N, M \le 2000$)이 적힌 줄로 시작하며, 이는 각각 사진의 높이와 너비이다. 이어지는 $N$ 개의 줄에는 각각 $M$ 개의 정수가 있고, 그중 $i$ 번째 줄의 $j$ 번째 정수는 $i$ 번째 행, $j$ 번째 열 픽셀의 명암 $A_{i,j}$ ($0 \le A_{i,j} \le 65535$)이다. 한 줄의 정수들은 하나 이상의 공백으로 구분되며, 숫자 사이나 줄의 처음과 끝에 공백이 더 있을 수도 있다.

사진 목록은 두 개의 $0$ 이 적힌 줄로 끝나며, 이 줄은 사진이 아니므로 처리하지 않는다.

각 사진에 대해, 그 사진에서 가장 큰 행 그라디언트, 열 그라디언트, 또는 대각선 광산의 넓이(픽셀 개수)를 한 줄에 하나의 정수로 출력한다.