#B3653. [语言月赛202208] 俊俏地鼠的远亲

[语言月赛202208] 俊俏地鼠的远亲

题目背景

地鼠十分想要找到自己远方的亲戚!

题目描述

非洲同胞永远是我们的好朋友。在东非草原上,一共有 n×mn\times m 只地鼠,他们生活的窝排列成 n×mn\times m 网格型。

其中,每只地鼠都有一个特征值 bi,jb_{i,j},经调查,我们认为特征值相同的地鼠一定有某种血缘关系。例如,两只地鼠分别生活在第二行第三列、第五行第六列。若 b2,3=b5,6b_{2,3}=b_{5,6},那么我们认为这两只地鼠是亲戚。

现在,给出这个 n×mn\times m 只地鼠的位置,需要对每只地鼠求出离自己距离最远的亲戚的距离是多少。

注意,假设两只地鼠分别位于第 ii 行第 jj 列和第 aa 行第 bb 列,则它们之间的距离为 (ia)2+(bj)2(i-a)^2+(b-j)^2

输入格式

第一行两个正整数 n,mn,m,表示地鼠家族的行数和列数。

2n+12\sim n+1 行给出一张大小为 n×mn\times m 的数表 {bn,m}\{b_{n,m}\},其中 bi,jb_{i,j} 表示第 iijj 列上地鼠的特征值。

输出格式

输出同样是一个 n×mn\times m 的数表,其中每个元素表示距自己最远的亲戚的距离是多少。

特别的,如果有某只地鼠没有远亲,则输出 00

2 4
1 2 3 2
3 2 1 3
5 4 5 5
9 5 5 9

提示

对于 30%30\% 的数据,1n,m31\leq n,m \leq 3

对于另外 10%10\% 的数据,有 n=1n=1

对于另外 10%10\% 的数据,有 m=1m=1

对于另外 10%10\% 的数据,有 bi,j=1b_{i,j}=1

对于 100%100\% 的数据,1n,m501\leq n,m\leq 501bi,j10181\leq b_{i,j}\leq 10^{18}