Game of doubling is actually more a puzzle than a game. The game board is a rectangle divided into fields that are unit squares. At the beginning, some fields contain a token, and some do not.

The player's objective is to gather a highest number of tokens in a single field. The only possible move is to locate two fields adjoining sides that contain the same (positive) number of tokens and transfer all tokens from one of these fields onto the other.

Write a program that for a given initial board configuration, would determine for each field the maximum number of tokens a player could accumulate in this field.

Input

The first line contains two integers $n$ and $m$ ($1 \le n,m \le 200$) indicating the number of rows and number of columns of the board. Each of the following $n$ lines contains a sequence of $m$ digits: 0 or 1. The digit 1 indicates a field containing a token, and the digit 0 indicates an empty field.

Output

Your program must output $n$ lines each containing $m$ integers. The $j$-th number in the $i$-th row should indicate the maximum number of tokens that a player could accumulate on the field located at the intersection $i$-th row and $j$-th column, starting from the given initial configuration.

Examples

Input

3 4
0111
1011
1011

Output

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

Explanation

The above example explains how to collect 4 tokens at a field positioned at the intersection of the middle row and the last column.