기본 벽 미로

이 문제에서는 다음으로 이루어진 아주 간단한 미로를 풀어야 합니다.

1. $6 \times 6$ 크기의 단위 정사각형 격자
2. 길이가 $1$ 이상 $6$ 이하의 정수인 벽 3개. 각 벽은 격자선을 따라 가로 또는 세로로 놓여 칸을 나눕니다.
3. 시작 표식과 도착 표식 각각 하나씩. 각 표식은 한 칸을 차지합니다.

예시 미로는 다음과 같습니다.

시작 표식이 있는 칸에서 도착 표식이 있는 칸까지의 최단 경로를 찾아야 합니다. 이동은 인접한 두 칸 사이에서만 가능하며, 두 칸이 인접하다는 것은 변을 공유하고 그 변이 벽으로 막혀 있지 않다는 뜻입니다. 격자 밖으로는 나갈 수 없습니다.

입력은 여러 개의 테스트 케이스로 이루어집니다.

각 테스트 케이스는 다섯 줄로 구성됩니다.

• 첫째 줄: 시작 표식이 있는 칸의 열과 행.
• 둘째 줄: 도착 표식이 있는 칸의 열과 행.
• 셋째, 넷째, 다섯째 줄: 각각 벽 하나의 위치.

칸은 왼쪽에서부터 센 열 번호 $1 \dots 6$ 과 위에서부터 센 행 번호 $1 \dots 6$ 으로 나타냅니다.

각 벽은 두 끝점으로 주어집니다. 가로 벽은 왼쪽 끝점을 먼저, 오른쪽 끝점을 나중에 적고, 세로 벽은 위쪽 끝점을 먼저, 아래쪽 끝점을 나중에 적습니다. 각 끝점은 격자 왼쪽 변으로부터의 거리와 격자 위쪽 변으로부터의 거리, 두 정수(둘 다 $0 \dots 6$)로 주어집니다.

세 벽은 서로 교차하지 않지만 격자의 모서리에서 맞닿을 수는 있으며, 모든 끝점은 격자 위에 있습니다. 시작 표식에서 도착 표식까지의 유효한 경로는 항상 존재합니다.

마지막 테스트 케이스 다음에는 $0$ 두 개가 적힌 줄이 오며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 시작 표식에서 도착 표식까지의 최단 경로 하나를 한 줄에 출력합니다.

경로는 이동을 나타내는 문자열로 적으며, 각 이동은 다음 중 하나입니다.

• N — 위로 한 칸
• E — 오른쪽으로 한 칸
• S — 아래로 한 칸
• W — 왼쪽으로 한 칸

최단 경로가 여러 개일 수 있습니다. 답을 유일하게 만들기 위해, 문자열을 일반 텍스트로 비교했을 때 사전순으로 가장 앞서는 최단 경로 문자열을 출력합니다. 이때 이동 문자의 순서는 E < N < S < W 입니다.

시작 표식과 도착 표식이 같은 칸에 있으면 경로는 비어 있으므로 빈 줄을 출력합니다.