Zając Trampler uwielbia deptać pola. Właśnie znalazł nowe, dobre pole. Jak widać na mapie, pole jest prostokątem o wysokości $H$ komórek i szerokości $W$ komórek. Gdy Trampler wejdzie do komórki, zadeptuje ją do ostatniej gałązki. Zajmuje mu to trochę czasu, określonego osobno dla każdej komórki.

Trampler nie wie jeszcze, skąd zacząć, ale ustalił już kolejność ruchów. Zapisał ją na kartce, oznaczając każdy podstawowy ruch literą.

Są różne rodzaje ruchów:

• litera U: przejdź z bieżącej komórki pola do komórki bezpośrednio nad nią;
• litera R: przejdź do sąsiedniej komórki po prawej;
• litera L: przejdź do sąsiedniej komórki po lewej;
• litera D: przejdź do sąsiedniej komórki poniżej.

Dla każdej komórki Trampler chce poznać czas potrzebny na wykonanie planu, jeśli rozpocznie trasę deptania w tej komórce. Spędzi pewien czas w komórce początkowej i w każdej kolejnej, nawet jeśli została już wcześniej zadeptana.

Nie zamierza opuszczać pola, dopóki nie skończy. Jeśli rozpoczęcie w pewnej komórce oznacza konieczność późniejszego opuszczenia pola, komórka ta nie nadaje się na punkt startowy. Trampler chce oznaczyć takie komórki liczbą $0$.

Wejście

Pierwszy wiersz pliku wejściowego określa liczbę całkowitą $T$ — liczbę przypadków testowych ($1 \le T \le 100$). Następnie występuje $T$ bloków.

Pierwszy wiersz bloku zawiera dwie liczby całkowite $H$ i $W$ — odpowiednio wysokość i szerokość pola ($1 \le H, W \le 100$).

Drugi wiersz bloku zawiera niepusty ciąg ruchów. Każdy ruch jest reprezentowany przez jeden z symboli L, R, U, D. Liczba ruchów nie przekracza $100$.

Każdy z kolejnych $H$ wierszy zawiera $W$ liczb całkowitych — czas, jaki zając spędza w konkretnej komórce pola. Liczby te należą do zakresu od $1$ do $1\,000$.

Łączna liczba komórek we wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz $H$ wierszy po $W$ liczb całkowitych — odpowiedzi dla każdej komórki pola.

Przykład

Wejście 1

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

Wyjście 1

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

Wejście 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

Wyjście 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

Uwagi

Ilustracja w treści zadania przedstawia pole z pierwszego przykładu oraz kierunki ruchów.