長耳大野兔 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

說明

題面入面幅圖畫咗第一個範例嘅田地同埋移動方向。