题目背景

本题和简单版的唯一区别在于数据范围不同

题目描述

给定一个 $n$ 行 $m$ 列的数字矩阵 $g$。
如果当前一个点在第 $i$ 行第 $j$ 列，则这个点可以移动到与这个格子相邻（上下左右）且与这个格子上的数字相同的格子上。
现在对于矩阵的每个格子，请求出一个点若初始在这个格子上，能访问到多少个格子？

输入格式

第一行两个整数 $n,m$。
接下来 $n$ 行，每行 $m$ 个整数，表示该数字矩阵 $g$。

输出格式

输出 $n$ 行，每行 $m$ 个数字。
第 $i$ 行第 $j$ 列表示若一个点从第 $i$ 行第 $j$ 列这个格子出发，能访问到多少个格子。

输入输出样例 #1

输入 #1

3 4
1 1 2 2
1 1 1 2
3 3 1 2

输出 #1

6 6 4 4
6 6 6 4
2 2 6 4

说明/提示

对于所有测试点，满足：$1\le n,m\le 1000,1\le g_{i,j}\le 10^9$。