长耳大野兔 Trampler 喜欢踩踏田地。他刚找到了一块不错的新田地。从地图上看，这块田地是一个高 $H$ 格、宽 $W$ 格的长方形。Trampler 进入一个格子后，会把里面的草木踩得一根不剩。这需要花费一些时间，每个格子所需的时间分别给定。

Trampler 还没决定从哪里开始，但他已经想好了移动顺序。他把顺序草草写在一张纸上，用一个字母表示每次基本移动。

移动有以下几种：

• 字母 U：从当前格子移动到正上方相邻的格子；
• 字母 R：移动到右侧相邻的格子；
• 字母 L：移动到左侧相邻的格子；
• 字母 D：移动到下方相邻的格子。

对于每个格子，Trampler 都想知道，如果从该格子开始踩踏路线，执行他的计划需要多少时间。他会在起始格子和随后经过的每个格子花费时间，即使那个格子已经被踩踏过。

在完成之前，他不打算离开田地。如果从某个格子开始会导致他最终不得不离开田地，这个格子就不适合作为起点。Trampler 希望把这样的格子标记为 $0$。

输入格式

输入文件第一行给出一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。随后有 $T$ 个数据块。

每个数据块的第一行包含两个整数 $H$ 和 $W$，分别表示田地的高度和宽度（$1 \le H, W \le 100$）。

数据块的第二行包含一个非空的移动序列。每次移动用 L、R、U、D 中的一个字符表示。移动次数不超过 $100$。

接下来的 $H$ 行，每行包含 $W$ 个整数，表示野兔在田地中各个格子花费的时间。这些数在 $1$ 到 $1\,000$ 之间。

所有测试用例的格子总数不超过 $10^5$。

输出格式

对于每个测试用例，输出 $H$ 行，每行 $W$ 个整数，表示田地中每个格子的答案。

样例

输入格式 1

1
3 4
RDRUL
2 9 7 4
5 8 6 5
6 4 6 2

输出格式 1

41 38 0 0
37 33 0 0
0 0 0 0

输入格式 2

2
1 1
D
1
5 5
RLDULRUD
4 7 8 5 8
7 9 9 5 7
3 8 5 3 6
1 6 6 9 3
5 2 1 6 1

输出格式 2

0
0 0 0 0 0
0 76 72 49 0
0 63 51 40 0
0 47 51 63 0
0 0 0 0 0

说明

题面中的插图展示了第一个样例中的田地以及移动方向。