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

给你一个 $n \times m$ 的二进制网格$^{\text{∗}}$ $G$。

我们定义一个矩形为一个满足以下条件的四元组 $(u,d,l,r)$：

• $1 \le \boldsymbol{u \lt d} \le n$；
• $1 \le \boldsymbol{l \lt r} \le m$；
• 单元格 $(u,l)$、$(u,r)$、$(d,l)$、$(d,r)$ 均包含数字 $1$。

那么，矩形 $(u,d,l,r)$ 的面积定义为 $(d-u+1) \cdot (r-l+1)$。

例如，考虑下面给出的二进制网格：

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

此处，你可以看到两个矩形 $(1,2,1,3)$ 和 $(1,3,3,5)$$^{\text{†}}$，其面积分别为 $6$ 和 $9$。

对每个单元格 $(i,j)$，求满足 $u \le i \le d$ 且 $l \le j \le r$ 的任意矩形 $(u,d,l,r)$ 的最小面积。

$^{\text{∗}}$二进制网格是一个每个单元格只含 $0$ 或 $1$ 的网格。第 $i$ 行第 $j$ 列的单元格记为 $(i,j)$。

$^{\text{†}}$注意，该网格中仅存在这两个矩形；例如，$(1,1,1,5)$ 不是矩形，因为它不满足 $u \lt d$。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n,m$，且 $n\cdot m \le 250\,000$）。

接下来的 $n$ 行中，每行包含一个长度为 $m$ 的字符串，表示矩阵 $G$ 的第 $i$ 行（其中 $G_{i,j} \in \{0,1\}$）。

保证所有测试用例的 $n\cdot m$ 之和不超过 $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.

对于每个测试用例，输出一个 $n$ 行 $m$ 列的网格。在第 $i$ 行第 $j$ 列的位置上，应输出：

• 若存在矩形 $(u,d,l,r)$ 满足 $u \le i \le d$ 且 $l \le j \le r$，则输出所有满足条件的矩形的最小面积；
• 否则，输出 $0$。

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

第一个测试用例已在题目描述中说明。

对于第三个测试用例，共有六个矩形覆盖至少一个单元格且面积最小：

• $(1,3,1,2)$，其面积为 $6$；
• $(1,2,1,3)$，其面积为 $6$；
• $(3,4,2,3)$，其面积为 $4$；
• $(2,3,3,4)$，其面积为 $4$；
• $(3,5,4,5)$，其面积为 $6$；
• $(4,5,3,5)$，其面积为 $6$。