CF2055C.The Trail

There are no mountains in Florida, and Florida Man cannot comprehend their existence. As such, he really needs your help with this one.

In the wilderness lies a region of mountainous terrain represented as a rectangular grid with $n$ rows and $m$ columns. Each cell in the grid is identified by its position $(i, j)$, where $i$ is the row index and $j$ is the column index. The altitude of cell $(i, j)$ is denoted by $a_{i,j}$.

However, this region has been tampered with. A path consisting of $n + m - 1$ cells, starting from the top-left corner $(1, 1)$ and ending at the bottom-right corner $(n, m)$, has been cleared. For every cell $(i, j)$ along this path, the altitude $a_{i,j}$ has been set to $0$. The path moves strictly via downward ($\mathtt{D}$) or rightward ($\mathtt{R}$) steps.

To restore the terrain to its original state, it is known that the region possessed a magical property before it was tampered with: all rows and all columns shared the same sum of altitudes. More formally, there exists an integer $x$ such that $\sum_{j=1}^m a_{i, j} = x$ for all $1\le i\le n$, and $\sum_{i=1}^n a_{i, j} = x$ for all $1\le j\le m$.

Your task is to assign new altitudes to the cells on the path such that the above magical property is restored. It can be proven that a solution always exists. If there are multiple solutions that satisfy the property, any one of them may be provided.

佛罗里达州没有山脉，而“佛罗里达男子”无法理解山脉的存在。因此，他非常需要你在此问题上的帮助。

野外有一片山地地形，以一个 $n$ 行 $m$ 列的矩形网格表示。网格中每个单元格由其位置 $(i, j)$ 标识，其中 $i$ 为行索引，$j$ 为列索引。单元格 $(i, j)$ 的海拔高度记为 $a_{i,j}$。

然而，该区域已被人为篡改：一条由 $n + m - 1$ 个单元格组成的路径已被清理，该路径从左上角 $(1, 1)$ 出发，终止于右下角 $(n, m)$。对于该路径上的每一个单元格 $(i, j)$，其海拔高度 $a_{i,j}$ 均被设为 $0$。该路径仅允许向下（$\mathtt{D}$）或向右（$\mathtt{R}$）移动。

为了将地形恢复至原始状态，已知该区域在被篡改前具有一种神奇性质：所有行与所有列的海拔高度之和均相等。更准确地说，存在某个整数 $x$，使得对所有 $1 \le i \le n$，有 $\sum_{j=1}^m a_{i, j} = x$；且对所有 $1 \le j \le m$，有 $\sum_{i=1}^n a_{i, j} = x$。

你的任务是为路径上的各单元格重新指定海拔高度，使得上述神奇性质得以恢复。可以证明，解一定存在。若存在多个满足条件的解，则输出任意一个即可。

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 \leq n, m \leq 1000$) — the number of rows and columns in the grid.

The second line of each test case contains a string $s$ of length $n+m-2$ ($s_i = \mathtt{D}$ or $s_i = \mathtt{R}$) — the steps the path makes from $(1, 1)$ to $(n, m)$. The character $\mathtt{D}$ represents a downward step, and $\mathtt{R}$ represents a rightward step.

The $i$-th of the next $n$ lines each contain $m$ integers $a_{i,1}, a_{i, 2}, \ldots, a_{i,m}$ ($-10^6 \leq a_{i,j} \leq 10^6$) — the altitude of each cell in the grid. It is guaranteed that if a cell $(i, j)$ lies on the path, then $a_{i,j} = 0$.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.

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

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 1000$）—— 分别表示网格的行数和列数。

每个测试用例的第二行包含一个长度为 $n+m-2$ 的字符串 $s$（其中每个字符 $s_i$ 为 $\mathtt{D}$ 或 $\mathtt{R}$）—— 表示从 $(1, 1)$ 到 $(n, m)$ 的路径所经过的步骤。字符 $\mathtt{D}$ 表示向下移动一步，$\mathtt{R}$ 表示向右移动一步。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i, 2}, \ldots, a_{i,m}$（$-10^6 \leq a_{i,j} \leq 10^6$）—— 表示网格中每个单元格的海拔高度。保证：若单元格 $(i, j)$ 位于该路径上，则 $a_{i,j} = 0$。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

For each test case, output $n$ lines of $m$ integers representing the restored grid of altitudes $b_{i, j}$. The altitudes must satisfy $-10^{15} \leq b_{i,j} \leq 10^{15}$, and additionally $a_{i,j} = b_{i,j}$ if $(i, j)$ is not on the path. If multiple solutions exist, output any of them.

对于每个测试用例，输出 $n$ 行，每行 $m$ 个整数，表示恢复后的海拔高度网格 $b_{i, j}$。海拔高度必须满足 $-10^{15} \leq b_{i,j} \leq 10^{15}$，且当 $(i, j)$ 不在路径上时，还需满足 $a_{i,j} = b_{i,j}$。若存在多个解，输出其中任意一个即可。

In the first test case, the grid has been filled such that every row and column contains the numbers $1, 2, 3$ in some order, resulting in a common sum of $6$.

In the second test case, the grid has been filled such that all rows and columns sum to $0$.

在第一个测试用例中，网格已填满，使得每行和每列都以某种顺序包含数字 $1, 2, 3$，从而得到共同的和 $6$。

在第二个测试用例中，网格已填满，使得所有行和列的和均为 $0$。