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

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

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.

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.