ジャックウサギの 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$）。

ブロックの 2 行目には空でない移動列が含まれます。各移動は文字 L、R、U、D のいずれかで表されます。移動回数は $100$ 以下です。

続く $H$ 行にはそれぞれ $W$ 個の整数が含まれ、ウサギが畑の各マスで費やす時間を表します。これらの数は $1$ 以上 $1\,000$ 以下です。

すべてのテストケースにおけるマスの総数は $10^5$ 以下です。

出力

各テストケースについて、畑の各マスの答えを、各行 $W$ 個の整数からなる $H$ 行で出力してください。

入出力例

入力 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

注記

問題文の図は、最初の入出力例の畑と移動方向を示しています。