佛罗里达州没有山脉,佛罗里达人无法理解它们的存在。因此,他在这件事上确实需要你的帮助。
在荒野中,有一个山区地形区域,表示为具有 $$$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$$$。
你的任务是为路径上的单元格分配新的高度,以便恢复上述魔法属性。可以证明,解总是存在的。如果存在多个满足该性质的解,则可以提供其中任何一个。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n, m \leq 1000$$$) - 网格中的行数和列数。
每个测试用例的第二行包含一个长度为 $$$n+m-2$$$ 的字符串 $$$s$$$($$$s_i = \mathtt{D}$$$ 或 $$$s_i = \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$$$。
输出
对于每个测试用例,输出 $$$n$$$ 行 $$$m$$$ 整数,表示恢复的海拔高度网格 $$$b_{i, j}$$$。海拔高度必须满足 $$$-10^{15} \leq b_{i,j} \leq 10^{15}$$$,并且如果 $$$(i, j)$$$ 不在路径上,则另外 $$$a_{i,j} = b_{i,j}$$$ 。如果存在多个解,则输出其中任何一个。
示例
输入 #1
4 3 3 DRRD 0 2 3 0 0 0 3 1 0 4 5 DRRRRDD 0 1 0 2 3 0 0 0 0 0 -1 0 -3 -3 0 0 0 0 -1 0 2 3 RRD 0 0 0 0 1 0 5 5 DDDDRRRR 0 25 2 9 11 0 6 13 20 22 0 17 24 1 8 0 3 10 12 19 0 0 0 0 0
输出 #1
1 2 3 2 3 1 3 1 2 -6 1 0 2 3 7 -1 3 2 -11 -1 0 -3 -3 7 0 0 0 -1 1 0 -1 1 0 1 -1 18 25 2 9 11 4 6 13 20 22 15 17 24 1 8 21 3 10 12 19 7 14 16 23 5
注意
在第一个测试用例中,网格已被填充,使得每行和每列都按某种顺序包含数字 $$$1, 2, 3$$$,从而得到公共总和 $$$6$$$。
在第二个测试用例中,网格已被填充,使得所有行和列的总和为 $$$0$$$。