La liebre Trampler adora pisotear campos. Acaba de encontrar un buen campo nuevo. Como se ve en el mapa, el campo es un rectángulo de $H$ celdas de alto y $W$ celdas de ancho. Cuando Trampler entra en una celda, la pisotea hasta la última ramita. Esto le lleva un tiempo, definido por separado para cada celda.

Trampler no sabe por dónde empezar, pero ya ha decidido la secuencia de movimientos. La ha garabateado en un papel, marcando cada movimiento elemental con una letra.

Hay distintos tipos de movimientos:

• letra U: moverse desde la celda actual del campo a la celda inmediatamente superior;
• letra R: moverse a la celda adyacente de la derecha;
• letra L: moverse a la celda adyacente de la izquierda;
• letra D: moverse a la celda adyacente de abajo.

Para cada celda, Trampler necesita saber el tiempo necesario para ejecutar su plan si comienza su recorrido de pisoteo en esa celda. Pasará cierto tiempo en la celda inicial y en cada celda posterior, incluso si ya la había pisoteado antes.

No planea salir del campo hasta terminar. Si comenzar en una celda implica tener que salir del campo en algún momento, esa celda no sirve como punto de partida. Trampler quiere que esas celdas se marquen con $0$.

Entrada

La primera línea del archivo de entrada define un entero $T$: el número de casos de prueba ($1 \le T \le 100$). Le siguen $T$ bloques.

La primera línea de un bloque contiene dos enteros $H$ y $W$: la altura y la anchura del campo, respectivamente ($1 \le H, W \le 100$).

La segunda línea del bloque contiene una secuencia no vacía de movimientos. Cada movimiento se representa mediante uno de los símbolos L, R, U, D. El número de movimientos es como máximo $100$.

Cada una de las siguientes $H$ líneas contiene $W$ enteros: el tiempo que la liebre pasa en una celda específica del campo. Estos números están entre $1$ y $1\,000$, ambos inclusive.

El número total de celdas en todos los casos de prueba es como máximo $10^5$.

Salida

Para cada caso de prueba, imprime $H$ líneas de $W$ enteros: las respuestas para cada una de las celdas del campo.

Ejemplos

Entrada 1

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

Salida 1

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

Entrada 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

Salida 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

Nota

La ilustración del enunciado muestra el campo del primer ejemplo y las direcciones de los movimientos.