加倍游戏与其说是一个游戏，不如说是一个谜题。游戏板是一个矩形，分成单位正方形的格子。开始时，一些格子包含筹码，一些不包含。

玩家的目标是在一个格子上收集尽可能多的筹码。唯一可用的移动是找到两个侧面相邻的格子，它们包含相同（正）数量的筹码，并将其中一个格子上的所有筹码移动到另一个格子上。

编写一个程序，给定板的初始配置，对于每个格子，确定玩家可以在该格子上收集的最大筹码数量。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \leq n,m \leq 200$)，表示板的行数和列数。接下来的 $n$ 行，每行包含一个由 $m$ 个数字 0 或 1 组成的字符串。数字 1 表示包含筹码的格子，数字 0 表示空闲格子。

输出格式

你的程序应该输出 $n$ 行，每行包含 $m$ 个整数。第 $i$ 行的第 $j$ 个数字应该表示玩家从给定初始配置开始，可以在位于第 $i$ 行和第 $j$ 列交叉处的格子上收集的最大筹码数量。

例子

输入

3 4
0111
1011
1011

输出

0 2 4 4
2 0 4 4
2 0 4 4

解释

以上示例解释了如何在中间行和最后一列交叉处的格子上收集 4 个筹码。