회전하는 펭귄 미로

아기 펭귄을 미로 안에 숨겨 둔 물고기까지 최대한 빨리 데려가려고 한다. 펭귄은 나침반을 읽을 줄 알아서 E, N, W, S 네 가지 명령을 알아듣고, 명령 하나마다 그 방향으로 한 칸 움직인다.

미로에는 장치가 하나 더 있다. 일부 칸에는 압력판이 깔려 있고, 펭귄이 그런 칸을 밟으면 미로가 놓인 빙산 전체가 반시계 방향으로 90도 돈다. 펭귄은 빙산과 함께 돌기 때문에 회전을 알아채지 못한다. 반면 나침반 바늘은 빙산을 따라 돌지 않는다. 그래서 압력판이 작동할 때마다 남은 명령을 바꿔서 줘야 한다.

미로는 항상 시작 칸에서 도착 칸까지 가는 길이 정확히 하나다. 어느 두 칸 사이에도 길이 정확히 하나씩 있고, 시작 칸에는 압력판이 없다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 미로의 가로 크기 $X$와 세로 크기 $Y$가 주어진다. 다음 줄에는 펭귄의 시작 좌표와 물고기가 있는 칸의 좌표를 나타내는 네 정수 $p_x$, $p_y$, $g_x$, $g_y$가 주어진다. 이어서 $Y$개의 줄에 각각 $X$개의 문자가 주어진다.

문자 하나가 칸 하나를 나타낸다. 값은 32진수 한 자리($0$, $1$, ..., $9$, $A$, $B$, ..., $V$)로 적혀 있고, 그 칸이 가진 요소의 합이다. 동쪽으로 통로가 있으면 $1$, 북쪽으로 있으면 $2$, 서쪽으로 있으면 $4$, 남쪽으로 있으면 $8$을 더한다. 압력판이 있으면 $16$(문자로는 $G$)을 더한다. 예를 들어 칸 값이 $H$, 즉 $17$이면 그 칸에는 동쪽 통로와 압력판이 있다.

$x$ 좌표는 왼쪽에서 오른쪽으로, $y$ 좌표는 위에서 아래로 커진다. 위에서 $y+1$번째 줄의 왼쪽에서 $x+1$번째 문자가 칸 $(x, y)$이고, 북쪽은 $y$가 줄어드는 방향이다.

• $0 < T \le 100$
• $0 < X \le 500$
• $0 < Y \le 500$
• $0 \le p_x, g_x < X$
• $0 \le p_y, g_y < Y$

각 테스트 케이스마다 한 줄에, 펭귄을 물고기가 있는 칸까지 최단 경로로 데려가는 나침반 명령을 순서대로 붙여서 출력한다. 명령 하나는 펭귄을 그 방향으로 정확히 한 칸 움직인다. 펭귄이 이미 물고기가 있는 칸에 서 있으면 빈 줄을 출력한다.