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

說明

題面中的插圖展示了第一個範例中的田地以及移動方向。