Background

Description

有一块矩形土地被划分成 n * m 个正方形小块。这些小块高低不平，每一小块都有自己的高度。水流可以由任意一块地流向周围四个方向的四块地中，但是不能直接流入对角相连的小块中。
一场大雨后，由于地势高低不同，许多地方都积存了不少降水。给定每个小块的高度，求每个小块的积水高度。
注意：假设矩形地外围无限大且高度为 0。

Format

Input

第一行包含两个非负整数 n,m。
接下来 n 行每行 m 个整数表示第 i 行第 j 列的小块的高度。

Output

输出 n 行，每行 m 个由空格隔开的非负整数，表示每个小块的积水高度。

Sample

Input

3 3 
4 4 0 
2 1 3 
3 3 -1

Output

0 0 0 
0 1 0 
0 0 1 

Limitation

对于 20%的数据 n,m<=4
对于 40%的数据 n,m<=15
对于 60%的数据 n,m<=50
对于 100%的数据 n,m<=300，|小块高度|<=10^9。
在每一部分数据中，均有一半数据保证小块高度非负
1s, 128000KiB for each test case.

Hint

Source

CDQZ TEST