408795: GYM103324 C RobôCIn

C. RobôCIntime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

O RobôCIn, grupo de pesquisa do Centro de Informática da UFPE que usa a robótica para resolver problemas, está desenvolvendo um novo projeto. Nesse projeto, eles criaram um robô que se locomove por um dado um tabuleiro retangular utilizando uma sequência de instruções. Porém, eles precisam de ajuda para descobrir onde o robô estará, considerando as dimensões do tabuleiro, a posição inicial do robô e o conjunto de instruções. A posição do robô consiste em um par de coordenadas x e y, que são inteiros, e uma orientação (N, S, L, O para norte, sul, leste e oeste) que indica pra qual lado o robô está virado no momento. Uma instrução para o robô é uma sequência de letras que pode ser "E", "D" e "F" que significam, respectivamente, as instruções:

• Esquerda: o robô virará 90 graus para a esquerda e permanecerá na mesma posição do tabuleiro.
• Direita: o robô virará 90 graus para a direita e permanecerá na mesma posição do tabuleiro.
• Frente: o robô avança para a próxima posição do tabuleiro na direção da orientação atual dele. Por exemplo, se a orientação atual dele é N (norte), a instrução F levaria o robô da posição (x, y) para a posição (x, y + 1).

Como o tabuleiro é retangular e limitado, caso o robô se mova para uma posição além dos limites, ele irá cair no abismo dos robôs. Sabendo disso, os alunos do RobôCIn implementaram, nos robôs, um sistema de aviso. Se um robô for cair para fora da área do tabuleiro, ele automaticamente marcará a posição que o levou a esse triste final. Dessa forma, os próximos robôs irão apenas ignorar uma instrução que o leve a cair a partir da mesma posição.Input

A primeira linha da entrada consiste nas coordenadas do canto superior direito. Assume-se que a posição (0,0) dele é o canto inferior esquerdo. A próxima linha contem a quantidade de robôs que o time do RobôCIn ira treinar, em ordem. Então, para cada robô, serão duas linhas. Na primeira a posição e orientação inicial. E, na segunda, a sequência de comandos que o robô deve ler.

Output

Para cada robô (conjunto de posição e instruções) da entrada, você deve imprimir a posição final dele no tabuleiro seguido de sua orientação final, todos separados por um espaço em branco e uma quebra de linha no final. Se um robô cair da borda do tabuleiro, deve imprimir a palavra "PERDIDO" após a posição e orientação, na mesma linha.

ExampleInput

5 3
3
1 1 L
DFDFDFDF
3 2 N
FDDFEEFFDDFEE
0 3 O
EEFFFEFEFE

Output

1 1 L
3 3 N PERDIDO
2 3 S

Note

* Uma posição consiste de dois inteiros que especificam as coordenadas iniciais do robô seguida de uma orientação (N, S, L, O), todos separados por um espaço em branco na mesma linha. Uma instrução do robô é uma sequência de letras 'L', 'R' e 'F' em uma linha.

* No tabuleiro, apenas um robô pode andar de cada vez, ou seja, primeiro você precisa processar toda a sequência de um robô antes de ir para o próximo. Você pode assumir que todas as posições iniciais do robô estão dentro dos limites do tabuleiro especificado. O valor máximo para qualquer coordenada é 50. Todas as strings de instrução terão menos de 100 e pelo menos 1 caracteres de comprimento.