미로 빠져나가기 (큰 버전)

로봇 에디슨은 오른손도 없고 눈도 없다. 그래서 걸을 때나 몸을 돌릴 때나 언제나 왼손을 벽에 대고 움직인다. 뒤로 걷는 것은 위험하다고 여겨서 절대 하지 않는다.

에디슨은 $N \times N$ 칸짜리 정사각형 미로 안에 있다. 미로 바깥은 사방이 벽으로 막혀 있고, 미로 안의 일부 칸도 벽이다. 에디슨은 빈 칸 사이를 북, 남, 서, 동 네 방향으로만 옮겨 다닌다.

에디슨은 왼손을 벽에 댄 채 벽을 따라 걸어서 미로를 빠져나가려고 한다. 어떤 칸에 서 있을 때 에디슨은 지금 바라보는 방향을 기준으로 왼쪽, 정면, 오른쪽, 뒤쪽 순서로 살펴보고, 빈 칸이 있는 첫 번째 방향으로 몸을 돌린 다음 그 칸으로 한 칸 걸어간다. 방금 걸어간 방향이 새로 바라보는 방향이 된다. 네 방향이 모두 벽이면 에디슨은 더 움직이지 못한다.

에디슨이 10,000걸음 이하로 출구 칸에 닿을 수 있는지 판정하고, 닿을 수 있으면 그 경로를 출력하라. 출구 칸에 서기만 하면 미로를 빠져나온 것으로 본다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 미로의 크기 $N$이 주어진다. 이어지는 $N$개의 줄에는 각각 $N$개의 문자가 주어진다. .은 빈 칸, #은 벽이다. 그다음 줄에는 네 정수 $sx$, $sy$, $ex$, $ey$가 주어진다. 에디슨은 $sx$행 $sy$열에서 출발하고, $ex$행 $ey$열이 출구다. 왼쪽 위 칸의 위치가 $(1, 1)$이다.

제한

• $1 \le T \le 30$
• $2 \le N \le 100$
• $1 \le sx, sy, ex, ey \le N$
• 출발 칸 $(sx, sy)$는 미로의 네 모서리 중 하나다.
• 출발 칸과 출구는 둘 다 빈 칸이고, 서로 다른 칸이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호다. 에디슨이 10,000걸음 안에 출구에 닿지 못하면 $y$는 따옴표를 뺀 Edison ran out of energy. 이고, 닿으면 $y$는 걸음 수이며 그다음 줄에 $y$개의 문자로 경로를 출력한다. 경로의 각 문자는 동쪽이 E, 남쪽이 S, 서쪽이 W, 북쪽이 N이다. 제자리에서 몸을 돌리는 동작은 세지도 않고 출력하지도 않는다.

출발할 때 에디슨의 왼손은 상하좌우로 맞닿은 네 칸 중 한 벽이나 미로 바깥 벽에 닿아 있다. 대각선으로만 맞닿은 칸은 손이 닿은 것으로 치지 않는다.

출발 칸이 모서리라서 네 방향 가운데 두 방향은 항상 미로 바깥 벽이다. 그래서 왼손이 벽에 닿는 처음 방향이 여럿이더라도 위 규칙이 만드는 경로는 모두 같다.