A lebre Trampler adora pisotear campos. Acabou de encontrar um bom campo novo. Como se vê no mapa, o campo é um retângulo com $H$ células de altura e $W$ células de largura. Quando Trampler entra numa célula, pisoteia-a até ao último galho. Isso leva algum tempo, definido individualmente para cada célula.

Trampler não sabe onde começar, mas já determinou a sequência de movimentos. Rabiscou-a numa folha de papel, assinalando cada movimento elementar com uma letra.

Há diferentes tipos de movimentos:

• letra U: mover-se da célula atual do campo para a célula imediatamente acima;
• letra R: mover-se para a célula adjacente à direita;
• letra L: mover-se para a célula adjacente à esquerda;
• letra D: mover-se para a célula adjacente abaixo.

Para cada célula, Trampler precisa de saber o tempo necessário para executar o seu plano se começar o percurso de pisoteio nessa célula. Passará algum tempo na célula inicial e em cada célula seguinte, mesmo que essa célula já tenha sido pisoteada.

Ele não planeia sair do campo antes de terminar. Se começar numa certa célula significar ter de sair do campo em algum momento, essa célula não serve como ponto de partida. Trampler quer que essas células sejam assinaladas com $0$.

Entrada

A primeira linha do ficheiro de entrada define um inteiro $T$ — o número de casos de teste ($1 \le T \le 100$). Seguem-se $T$ blocos.

A primeira linha de um bloco contém dois inteiros $H$ e $W$ — a altura e a largura do campo, respetivamente ($1 \le H, W \le 100$).

A segunda linha do bloco contém uma sequência não vazia de movimentos. Cada movimento é representado por um dos símbolos L, R, U, D. O número de movimentos não ultrapassa $100$.

Cada uma das próximas $H$ linhas contém $W$ inteiros — o tempo que a lebre passa numa célula específica do campo. Estes números vão de $1$ a $1\,000$, inclusive.

O número total de células em todos os casos de teste não ultrapassa $10^5$.

Saída

Para cada caso de teste, imprima $H$ linhas com $W$ inteiros — as respostas para cada uma das células do campo.

Exemplos

Entrada 1

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

Saída 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

Saída 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

A ilustração no enunciado mostra o campo do primeiro exemplo e as direções dos movimentos.