Description

给你一个 $n * m$ 的数字矩阵，现在有一条 $(1, 1)$ 到 $(n, m)$ 的路径被置零，现在请你填充这条路径，要求满足矩阵所有行列求和相等，输出任意的填充方法即可，不存在则输出 $-1$

Format

Input

第一行输入一个 $t$ 表示测试用例数量

对于每个测试：

第一行输入两个数字 $n$ 和 $m$ 表示矩阵大小

第二行输入一个字符串表示路径，$D$ 表示向下移动一格 ，$R$ 表示向右移动一格

接下来 $n$ 行每行 $m$ 个数 $a_{i,j}$ 表示矩阵 $a$

保证 $t$ 组测试 $n * m$ 之和不超过 $10^6$

Output

输出任意一个满足条件的矩阵，不在路径上的值不需要修改，要求输出的矩阵 $b$ 每个值 $b_{i,j}$ 满足 $\vert b_{i,j} \vert \leq 10^{15}$

Samples

1
3 3
RRDD
0 0 0
2 3 0
3 1 0

1 2 3
2 3 1
3 1 2

Limitation

$1 \leq t \leq 10^4$

$2 \leq n,m \leq 1000$

$\vert a_{i,j} \vert \leq 10^{6}$