흔들흔들 걷기

Banny는 방금 프로그래밍 가능한 새 로봇을 샀다. 자신의 코딩 실력을 시험해 보고 싶었던 그는 로봇을 R개의 행(북쪽에서 남쪽으로 1부터 R까지 번호가 매겨짐)과 C개의 열(서쪽에서 동쪽으로 1부터 C까지 번호가 매겨짐)로 이루어진 정사각형 격자에 놓았다. r행 c열의 칸은 (r, c)로 나타낸다.

처음에 로봇은 ($S_{R}$, $S_{C}$) 칸에서 시작한다. Banny는 로봇에게 N개의 명령을 내린다. 각 명령은 N, S, E, W 중 하나이며, 각각 로봇에게 북쪽, 남쪽, 동쪽, 서쪽으로 한 칸 이동하라고 지시한다.

로봇이 이전에 방문한 적이 있는 칸으로 이동하면, 이전에 방문한 적이 없는 칸에 도달할 때까지 같은 방향으로 계속 이동한다. Banny는 로봇이 격자 밖으로 이동하게 하는 명령을 절대 내리지 않는다.

로봇이 N개의 명령을 따른 뒤 어느 칸에서 끝나는지 Banny가 알아내도록 도와줄 수 있는가?

제한

메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ R ≤ 5 × $10^{4}$. 1 ≤ C ≤ 5 × $10^{4}$. 1 ≤ $S_{R}$ ≤ R. 1 ≤ $S_{C}$ ≤ C. 명령으로 인해 로봇이 격자 밖으로 이동하는 일은 없다.

테스트 세트 1 (공개)

시간 제한: 20초. 1 ≤ N ≤ 100.

테스트 세트 2 (비공개)

시간 제한: 60초. 1 ≤ N ≤ 5 × $10^{4}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 다섯 정수 N, R, C, $S_{R}$, $S_{C}$이 포함된 줄로 시작하며, 각각 명령의 수, 행의 수, 열의 수, 로봇이 시작하는 행과 열을 나타낸다.

그다음에는 N개의 문자로 이루어진 문자열 하나가 포함된 줄이 주어진다. 이 문자들 중 i번째 문자는 Banny가 로봇에게 내리는 i번째 명령이다(위에서 설명한 N, S, E, W 중 하나).

각 테스트 케이스마다 Case #x: r c을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), r은 로봇이 최종적으로 위치한 행이고 c는 로봇이 최종적으로 위치한 열이다.

예제 케이스 #1은 왼쪽 위 그림에, 예제 케이스 #2은 오른쪽 위 그림에, 예제 케이스 #3은 아래쪽 그림에 해당한다. 각 그림에서 노란색 칸은 로봇이 시작하는 칸이고, 초록색 칸은 로봇이 최종적으로 위치하는 칸이다.