Der Hase Trampler liebt es, Felder niederzutrampeln. Gerade hat er ein gutes neues Feld gefunden. Wie auf der Karte zu sehen ist, ist das Feld ein Rechteck mit $H$ Zellen Höhe und $W$ Zellen Breite. Wenn Trampler eine Zelle betritt, trampelt er sie bis zum letzten Zweig nieder. Das dauert eine Weile; diese Zeit ist für jede einzelne Zelle vorgegeben.

Trampler ist noch nicht sicher, wo er beginnen soll, aber die Folge seiner Bewegungen hat er bereits festgelegt. Er hat sie auf einen Zettel gekritzelt und jede einzelne Grundbewegung mit einem Buchstaben gekennzeichnet.

Es gibt verschiedene Arten von Bewegungen:

• Buchstabe U: von der aktuellen Feldzelle in die unmittelbar darüberliegende benachbarte Zelle gehen;
• Buchstabe R: in die benachbarte Zelle rechts gehen;
• Buchstabe L: in die benachbarte Zelle links gehen;
• Buchstabe D: in die benachbarte Zelle darunter gehen.

Für jede Zelle möchte Trampler wissen, wie viel Zeit er zur Ausführung seines Plans benötigt, wenn er seine Trampelroute in dieser Zelle beginnt. Er verbringt Zeit in der Anfangszelle und in jeder folgenden Zelle, selbst wenn diese bereits niedergetrampelt wurde.

Er hat nicht vor, das Feld zu verlassen, bevor er fertig ist. Wenn ein Start in einer bestimmten Zelle dazu führt, dass er schließlich das Feld verlassen muss, ist diese Zelle als Startpunkt ungeeignet. Trampler möchte solche Zellen mit $0$ kennzeichnen lassen.

Eingabe

Die erste Zeile der Eingabedatei gibt eine ganze Zahl $T$ an — die Anzahl der Testfälle ($1 \le T \le 100$). Darauf folgen $T$ Blöcke.

Die erste Zeile eines Blocks enthält zwei ganze Zahlen $H$ und $W$ — die Höhe beziehungsweise Breite des Feldes ($1 \le H, W \le 100$).

Die zweite Zeile des Blocks enthält eine nichtleere Folge von Bewegungen. Jede Bewegung wird durch eines der Zeichen L, R, U, D dargestellt. Die Anzahl der Bewegungen beträgt höchstens $100$.

Jede der folgenden $H$ Zeilen enthält $W$ ganze Zahlen — die Zeit, die der Hase in einer bestimmten Feldzelle verbringt. Diese Zahlen liegen im Bereich von $1$ bis einschließlich $1\,000$.

Die Gesamtanzahl der Zellen in allen Testfällen beträgt höchstens $10^5$.

Ausgabe

Gib für jeden Testfall $H$ Zeilen mit jeweils $W$ ganzen Zahlen aus — die Antworten für jede Zelle des Feldes.

Beispiele

Eingabe 1

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

Ausgabe 1

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

Eingabe 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

Ausgabe 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

Hinweis

Die Abbildung in der Aufgabenstellung zeigt das Feld aus dem ersten Beispiel und die Bewegungsrichtungen.