다이아몬드

$M$개의 행과 $N$개의 열로 이루어진 평면 격자를 생각하자. 이 격자에는 정확히 $MN$개의 교차점이 있으며, 각 교차점은 좌표쌍 $(i, j)$로 나타낸다. 여기서 $i = 0, 1, \ldots, N-1$은 열(즉 $x$좌표), $j = 0, 1, \ldots, M-1$은 행(즉 $y$좌표)이다.

이제 서로 다른 $K \le MN$개의 교차점에 점 $K$개를 놓는다.

다이아몬드 $D(i, j, r)$는 교차점 $(i, j)$를 중심으로 하며, 대각선 길이가 $2r$인 정사각형을 $45^\circ$ 회전시킨 마름모 모양이다. 반지름 $r$는 $r \ge 1$인 임의의 정수이다. 이는 곧 중심으로부터 맨해튼 거리가 $r$ 이하인 모든 점, 즉 $|x - i| + |y - j| \le r$를 만족하는 모든 점 $(x, y)$를 덮는 것과 같다.

각 $P_{\min} = 1, 2, \ldots, K$에 대하여, 중심을 어느 교차점에 놓더라도 항상 최소 $P_{\min}$개의 점을 덮는 것이 보장되는 가장 작은 반지름 $R_{\min}(P_{\min})$을 구하라. 다시 말해 $R_{\min}(P_{\min})$은, 모든 중심 위치에 대한 최악의 경우(덮는 점 개수의 최솟값)가 $P_{\min}$ 이상이 되게 하는 가장 작은 $r$이다.

$P_{\max}(P_{\min})$은 반지름이 $R_{\min}(P_{\min})$인 다이아몬드 하나가 덮을 수 있는 점의 최대 개수이다.

예를 들어 $5$행 $7$열 격자 위의 다섯 점 $(0,0)$, $(4,0)$, $(2,2)$, $(0,4)$, $(4,4)$를 생각하자. 다이아몬드 $D(2,4,1)$은 어떤 점도 덮지 않고, $D(2,1,2)$는 한 점을 덮으며, $D(3,3,4)$는 네 점을 덮는다.

첫째 줄에 행의 수 $M$과 열의 수 $N$이 주어진다.

이후 줄들에는 점 $K$개가 주어진다($K \le MN$). 각 점은 $x$좌표와 $y$좌표를 이 순서로 나타내는 두 정수로 주어진다. 점들은 한 줄 또는 여러 줄에 걸쳐 나올 수 있으며, 한 줄 안의 모든 값은 하나 이상의 공백 문자(스페이스 또는 탭)로 구분된다.

$1 \le M \le 100$, $1 \le N \le 100$임을 가정해도 된다. 격자 밖에 있는 점(즉 $x < 0$, $x > N-1$, $y < 0$, 또는 $y > M-1$)은 유효하지 않으므로 버린다.

먼저 세 열의 제목 Pmin, Rmin(Pmin), Pmax(Pmin)을 담은 머리글 줄을 출력하고, 이어서 조건을 만족하는 각 $P_{\min}$ 값마다 한 줄씩 출력한다.

어떤 $P_{\min}$ 값에 대해서는, 반지름이 $R_{\min}(P_{\min})$인 다이아몬드가 정확히 $P_{\min}$개의 점을 덮는 것이 보장될 때에만 $P_{\min}$, $R_{\min}(P_{\min})$, $P_{\max}(P_{\min})$의 세 값을 출력한다. 연속한 두 값이 같은 반지름을 가지면(예: $R_{\min}(2) = R_{\min}(3)$) 더 큰 값만 조건을 만족하므로, 더 작은 값에 대해서는 줄을 출력하지 않는다.

각 값은 해당 열 제목의 마지막 글자에 오른쪽 끝이 맞도록 오른쪽 정렬하며, 열과 열 사이는 두 칸의 공백으로 구분한다.