CF2194D.Table Cut

Given a table of size $n \times m$, where each cell contains either $0$ or $1$. The task is to divide it into two parts with a cut that goes from the top left corner to the bottom right corner. The cut lines can only go right or down.

Let $a$ be the number of ones in one part of the table after the cut, and $b$ be the number of ones in the other part of the table. The goal is to maximize the value of $a \cdot b$.

给定一个大小为 $n \times m$ 的表格，其中每个单元格包含 $0$ 或 $1$。任务是用一条从左上角到右下角的切割线将表格分为两部分，且切割线只能向右或向下延伸。

设切割后表格一部分中 $1$ 的个数为 $a$，另一部分中 $1$ 的个数为 $b$。目标是最大化 $a \cdot b$ 的值。

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$ ($1 \leq n, m \leq 3 \cdot 10^{5}$, $2 \leq n \cdot m \leq 3 \cdot 10^{5}$) — the number of rows and columns in the table, respectively.

Each of the following $n$ lines contains $m$ integers, where the $j$-th number in the $i$-th line corresponds to the value $a_{i, j}$ ($0 \leq a_{i, j} \leq 1$).

It is guaranteed that the sum of $n \cdot m$ across all test cases does not exceed $3 \cdot 10^{5}$.

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

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 3 \cdot 10^{5}$，且 $2 \leq n \cdot m \leq 3 \cdot 10^{5}$），分别表示表格的行数和列数。

接下来的 $n$ 行中，每行包含 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数对应值 $a_{i, j}$（$0 \leq a_{i, j} \leq 1$）。

保证所有测试用例的 $n \cdot m$ 之和不超过 $3 \cdot 10^{5}$。

For each test case, output a single number in the first line of the output data — the maximum value of the product.

In the second line, output a string consisting of $n$ characters 'D' and $m$ characters 'R', representing the direction of the next cut, where 'D' means a cut downwards, and 'R' — a cut to the right.

对于每个测试用例，在输出数据的第一行输出一个数字——乘积的最大值。

在第二行输出一个由 $n$ 个字符 'D' 和 $m$ 个字符 'R' 组成的字符串，表示下一次切割的方向，其中 'D' 表示向下切割，'R' 表示向右切割。

The images show the correct cuts for each of the first and second test cases, at which the maximum value of the product is achieved.

图片展示了第一个和第二个测试用例的正确切割方式，此时乘积的值达到最大。