B. Rectanglestime limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputYou 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 < d} \le n$$$; $$$1 \le \boldsymbol{l < 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<d$$$.InputEach 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$$$.OutputFor 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. ExampleInput33 51010110100001014 60111010100011000101011105 51110010110111110110100111Output6 6 6 9 96 6 6 9 90 0 9 9 90 10 8 8 10 100 10 8 8 10 1010 10 8 8 10 010 10 8 8 10 06 6 6 0 06 6 4 4 06 4 4 4 60 4 4 6 60 0 6 6 6NoteThe 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$$$.