B. Rectangles
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a binary grid$$$^{\text{∗}}$$$ $$$G$$$ of dimensions $$$n \times m$$$.

Let us define a rectangle as a tuple $$$(u,d,l,r)$$$ that satisfies the following conditions:

  • $$$1 \le \boldsymbol{u \lt d} \le n$$$;
  • $$$1 \le \boldsymbol{l \lt r} \le m$$$;
  • Cells $$$(u,l)$$$, $$$(u,r)$$$, $$$(d,l)$$$, $$$(d,r)$$$ all contain a $$$1$$$.

Then, the area of a rectangle $$$(u,d,l,r)$$$ is defined as $$$(d-u+1) \cdot (r-l+1)$$$.

For example, consider the following binary grid given below.

$$$$$$\begin{matrix} 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{matrix}$$$$$$

Here, you may see two rectangles $$$(1,2,1,3)$$$ and $$$(1,3,3,5)$$$$$$^{\text{†}}$$$, each of which has area $$$6$$$ and $$$9$$$, respectively.

For each cell $$$(i,j)$$$, find the minimum area of any rectangle $$$(u,d,l,r)$$$ such that $$$u \le i \le d$$$ and $$$l \le j \le r$$$.

$$$^{\text{∗}}$$$A binary grid is a grid where each cell contains $$$0$$$ or $$$1$$$. The cell on the $$$j$$$-th column of the $$$i$$$-th row is denoted as cell $$$(i,j)$$$.

$$$^{\text{†}}$$$Note that these are the only rectangles in the grid; for example, $$$(1,1,1,5)$$$ is not a rectangle as it does not satisfy $$$u \lt d$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n,m$$$, $$$n\cdot m \le 250\,000$$$).

Each of the $$$n$$$ following lines contains a string of length $$$m$$$ denoting the $$$i$$$-th row of $$$G$$$ ($$$G_{i,j} \in \{0,1\}$$$).

It is guaranteed that the sum of $$$n\cdot m$$$ over all test cases does not exceed $$$250\,000$$$.

Output

For each test case, output a grid of $$$n$$$ rows and $$$m$$$ columns. On the $$$j$$$-th column of the $$$i$$$-th row, you should output:

  • If there exists a rectangle $$$(u,d,l,r)$$$ such that $$$u \le i \le d$$$ and $$$l \le j \le r$$$, output the minimum area of any such rectangle;
  • Otherwise, output $$$0$$$ instead.
Example
Input
3
3 5
10101
10100
00101
4 6
011101
010001
100010
101110
5 5
11100
10110
11111
01101
00111
Output
6 6 6 9 9
6 6 6 9 9
0 0 9 9 9
0 10 8 8 10 10
0 10 8 8 10 10
10 10 8 8 10 0
10 10 8 8 10 0
6 6 6 0 0
6 6 4 4 0
6 4 4 4 6
0 4 4 6 6
0 0 6 6 6
Note

The first test case is explained in the statement.

For the third test case, there are six rectangles that cover at least one cell with minimum area:

  • $$$(1,3,1,2)$$$, which has area $$$6$$$;
  • $$$(1,2,1,3)$$$, which has area $$$6$$$;
  • $$$(3,4,2,3)$$$, which has area $$$4$$$;
  • $$$(2,3,3,4)$$$, which has area $$$4$$$;
  • $$$(3,5,4,5)$$$, which has area $$$6$$$;
  • $$$(4,5,3,5)$$$, which has area $$$6$$$.