CF2159B Rectangles

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 < 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

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 $ .

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.

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 $ .