Robôs em sincronia
Um depósito é uma grade com células livres (.) e paredes (#). Há robôs, numerados de 1 a , inicialmente em células livres distintas. Em cada uma de rodadas, todos recebem um comando: U, D, L, R ou S, respectivamente subir, descer, ir à esquerda, ir à direita ou ficar parado.
Resolva cada rodada usando exatamente estas regras, a partir das posições no começo da rodada:
- Um comando
S, ou um passo que sairia da grade ou entraria em uma parede, deixa o robô parado. Os demais robôs propõem um passo para a célula vizinha indicada. - Se dois ou mais robôs propõem entrar na mesma célula, todos eles têm seus movimentos cancelados e ficam parados. Considere apenas as propostas de passo do item 1; robôs que já estavam parados não fazem propostas.
- Cancele também todo movimento cujo destino seja a posição inicial de um robô que ficará parado. Repita essa regra até não ocorrer nenhum novo cancelamento. Propostas canceladas nunca voltam a ser consideradas.
- Execute simultaneamente todos os movimentos ainda não cancelados.
Assim, uma fila pode avançar para uma célula vazia, e robôs podem trocar de lugar ou girar em um ciclo, desde que nenhum dos movimentos envolvidos tenha sido cancelado. Informe a posição final de cada robô.
Input
A primeira linha contém , , e . As próximas linhas contêm a grade. Depois, há linhas com a linha e a coluna iniciais de cada robô, na ordem dos identificadores. Por fim, há palavras de caracteres: o caractere de uma palavra é o comando do robô naquela rodada.
Output
Imprima linhas. A linha deve conter a linha e a coluna finais do robô .
Samples
Sample 1
Input
3 4 3 2 .... .... .... 2 1 2 2 2 4 RRL RLS
Output
2 2 2 1 2 4
Na primeira rodada, os robôs 2 e 3 disputam a mesma célula. Eles param, impedindo também o movimento do robô 1. Na segunda rodada, os robôs 1 e 2 trocam de lugar.