로봇의 침공

평화를 사랑하는 팍스(Pax) 행성의 사람들이 사악한 구골(Googol) 행성의 침략자들과 전쟁을 벌이고 있습니다. 이들은 철저한 평화주의자이지만 스스로를 방어할 수단은 가지고 있습니다. 이들의 암호 해독가들은 구골이 로봇에게 보내는 명령을 일상적으로 해독할 수 있고, 막대한 에너지를 들이면 가짜 명령을 만들어 낼 수도 있습니다. 전술 방어대(TUD)는 구골의 명령 전송을 방해할 가장 좋은 방법을 찾아야 합니다.

지도 하나가 주어집니다. 지도에는 침입한 로봇 한 대가 있고, 장애물과 함정이 있을 수도 있습니다. 또한 로봇에게 원래 전송된 이동 명령 문자열이 주어집니다. 각 명령은 북·동·남·서 중 한 방향으로 한 칸 이동하라는 뜻입니다.

당신의 임무는 명령을 가능한 한 적게 수정하여 로봇을 함정으로 유도하는 것입니다. 한 번의 수정은 하나의 명령을 다른 방향으로 바꾸거나, 아무 이동도 하지 않는 것으로 바꾸는 것입니다.

이동 규칙. 어떤 명령에 대해, 이동하려는 칸이 지도 안에 있고 막혀 있지 않을 때에만 로봇은 그 방향으로 한 칸 움직입니다. 그렇지 않으면 로봇은 제자리에 머무릅니다.

로봇이 함정 칸에 들어서는 순간 붙잡힙니다.

첫 줄에는 시나리오의 개수가 주어집니다. 각 시나리오는 다음과 같이 주어집니다.

• 한 줄에 공백으로 구분된 두 정수 $w$와 $h$ ($1 \le w, h \le 100$): 지도의 너비와 높이.
• $h$개의 줄, 각 줄에 $w$개의 문자로 지도가 주어집니다. 정확히 한 칸이 R이며 로봇의 시작 위치입니다. 나머지 칸은 빈 칸을 뜻하는 ., 막힌 칸을 뜻하는 X, 함정을 뜻하는 +입니다.
• 한 줄에 정수 $c$ ($0 \le c \le 100$): 명령의 개수.
• 한 줄에 $c$개의 문자로 이루어진 원래 명령. 각 문자는 N, E, S, W이며 각각 위, 오른쪽, 아래, 왼쪽으로 한 칸 이동을 뜻합니다.

각 시나리오에 대해, 먼저 Scenario #i: 한 줄을 출력합니다. 여기서 i는 1부터 시작하는 시나리오 번호입니다.

그다음 줄에는 로봇을 함정으로 유도하는 수정된 명령 문자열을 출력합니다. 이 문자열은 정확히 $c$개의 문자로 이루어지며, 각 문자는 N, E, S, W, 또는 이동하지 않음을 뜻하는 X입니다. 로봇을 함정으로 유도하는 모든 문자열 중에서 다음 순서로 하나를 골라 출력합니다.

1. 원래 명령을 가장 적게 수정하는 것을 고르고,
2. 그중에서 로봇이 함정에 가장 일찍 도달하는 것을 고르고,
3. 그중에서 사전순으로 가장 앞서는 문자열을 고릅니다.

그러한 문자열이 존재하지 않으면 대신 impossible을 출력합니다.

연속한 시나리오 사이에는 빈 줄 하나를 넣어 구분합니다.