Pupil之路

题目描述

gq 是 Codeforces 的 newbie 选手，他在一次训练营中被派去维护一片虚拟山地地图以练习数据结构和数值推理。不幸的是，在一次“迷你打扫”活动中，gq 不小心把一条从左上角到右下角的路径全都铲平了 —— 路径上所有格子的高度都被设成了 0。现在他想修复地图，但他记得原地图有一个重要的性质：每一行的高度和与每一列的高度和都是相同的整数（gq 把这个神奇的数记作 x）。

你需要帮 gq 给被清空的路径上的格子重新赋高度，使得整张地图恢复 gq 记得的那个性质。题目保证至少存在一个可行解 —— 你只要输出任意一个满足条件的恢复后的地图即可。

如果 gq 顺利完成了任务，他就能继续参加训练营并成功成为 pupil 选手！

形式化的，你有一个 $n \times m$ 的网格，网格中的每个格子 $(i,j)$ 有一个整数高度 $a_{i,j}$。你还知道从 $(1,1)$ 到 $(n,m)$ 有一条路径，路径上所有格子的高度都被设成了 $0$。你需要将路径上格子的高度重新赋值为整数 $b_{i,j}$，使得：

• 存在一个整数 $x$，使得：
  • 对任意行 $i$，$\sum_{j=1}^m b_{i,j}=x$；
  • 对任意列 $j$，$\sum_{i=1}^n b_{i,j}=x$；
• 对任意不在路径上的格子 $(i,j)$，$b_{i,j}=a_{i,j}$。

如果有多种答案，输出任意一种即可。

输入格式

第一行包含一个整数 $t$，表示测试用例数。（$1 \le t \le 10^4$）

每个测试用例格式如下：

• 第一行：两个整数 $n$ 和 $m$（$2 \le n,m \le 1000$）。
• 第二行：字符串 $s$，长度为 $n+m-2$，每个字符为 D 或 R，表示从 $(1,1)$ 到 $(n,m)$ 的路径（D 表示向下，R 表示向右）。
• 接下来 $n$ 行，每行 $m$ 个整数 $a_{i,j}$（$-10^9 \le a_{i,j} \le 10^9$），表示网格当前的高度。题目保证路径上的格子在输入中均为 $0$。

保证所有测试用例中 $\sum n \cdot m \le 10^6$。

输出格式

对每个测试用例，输出 $n$ 行，每行 $m$ 个整数，表示修复后的高度矩阵 $b_{i,j}$，需要满足：

• 若 $(i,j)$ 不在路径上，则必须保持原值：$b_{i,j}=a_{i,j}$。
• 存在一个整数 $x$，使得对任意行 $i$，$\sum_{j=1}^m b_{i,j}=x$；对任意列 $j$，$\sum_{i=1}^n b_{i,j}=x$。
• 所有输出值满足 $-10^{18}\le b_{i,j}\le 10^{18}$。

若有多种答案，输出任意一种即可。

样例 1

3
3 3
DRRD
0 2 3
0 0 0
3 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 2 3
2 3 1
3 1 2
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,1）、（2,1）、（2,2）、（2,3）、（3,3）被清零，我们可以构造这样的网格已填充使得每一行和每一列都包含数字 $1, 2, 3$ 的某种排列，结果得到公共和为 $6$。

在第三个测试用例中，网格已填充使得所有行和列的和都为 $65$。