Le lièvre Trampler adore piétiner les champs. Il vient de trouver un beau nouveau champ. Comme on le voit sur la carte, ce champ est un rectangle de $H$ cases de haut et $W$ cases de large. Quand Trampler entre dans une case, il la piétine jusqu'à la dernière brindille. Cela lui prend du temps, et cette durée est définie séparément pour chaque case.

Trampler ne sait pas encore où commencer, mais il a déjà déterminé la suite de déplacements. Il l'a griffonnée sur un morceau de papier en représentant chaque déplacement élémentaire par une lettre.

Il existe différents types de déplacements :

• lettre U : passer de la case actuelle du champ à la case directement adjacente au-dessus ;
• lettre R : passer à la case adjacente de droite ;
• lettre L : passer à la case adjacente de gauche ;
• lettre D : passer à la case adjacente du dessous.

Pour chaque case, Trampler veut connaître le temps nécessaire pour exécuter son plan s'il commence son parcours de piétinement dans cette case. Il passera du temps dans la case initiale et dans chaque case suivante, même si celle-ci a déjà été piétinée.

Il ne prévoit pas de quitter le champ avant d'avoir terminé. Si partir d'une certaine case signifie devoir sortir du champ à un moment donné, cette case ne convient pas comme point de départ. Trampler souhaite que ces cases soient marquées par $0$.

Entrée

La première ligne du fichier d'entrée définit un entier $T$ — le nombre de cas de test ($1 \le T \le 100$). Elle est suivie de $T$ blocs.

La première ligne d'un bloc contient deux entiers $H$ et $W$ — la hauteur et la largeur du champ, respectivement ($1 \le H, W \le 100$).

La deuxième ligne du bloc contient une suite non vide de déplacements. Chaque déplacement est représenté par l'un des symboles L, R, U, D. Le nombre de déplacements ne dépasse pas $100$.

Chacune des $H$ lignes suivantes contient $W$ entiers — le temps que le lièvre passe dans une case particulière du champ. Ces nombres sont compris entre $1$ et $1\,000$, bornes incluses.

Le nombre total de cases dans tous les cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez $H$ lignes de $W$ entiers — les réponses pour chacune des cases du champ.

Exemples

Entrée 1

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

Sortie 1

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

Entrée 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

Sortie 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

Remarque

L'illustration de l'énoncé montre le champ du premier exemple et les directions des déplacements.