벽 미로 만들기

다음으로 이루어진 미로 제작 도구로 미로를 만듭니다.

1. 단위 정사각형으로 이루어진 6 × 6 격자
2. 길이가 1 이상 6 이하의 정수인 벽 3개. 각 벽은 가로 또는 세로로 놓여 인접한 두 칸 사이의 이동을 가로막습니다.
3. 출발 표식 1개와 도착 표식 1개

좌표계. 칸의 열 번호는 왼쪽에서 오른쪽으로 1부터 6까지, 행 번호는 위에서 아래로 1부터 6까지 매깁니다. 격자의 모서리(격자선의 교점)는 두 정수 (x, y)로 나타냅니다. 여기서 x는 격자 왼쪽 변으로부터의 거리(0 이상 6 이하), y는 격자 위쪽 변으로부터의 거리(0 이상 6 이하)입니다.

이동. 한 번의 이동은, 변을 맞대고 있으면서 그 변이 벽으로 막혀 있지 않은 인접한 칸으로만 갈 수 있으며, 격자 밖으로 나갈 수 없습니다. 이동 방향은 다음 네 가지입니다.

• N: 위쪽 칸으로(행 번호가 1 감소)
• S: 아래쪽 칸으로(행 번호가 1 증가)
• E: 오른쪽 칸으로(열 번호가 1 증가)
• W: 왼쪽 칸으로(열 번호가 1 감소)

벽. 길이가 L인 가로 벽은 어떤 가로 격자선 y 위에서 x1부터 x1 + L까지 놓입니다. 길이가 L인 세로 벽은 어떤 세로 격자선 x 위에서 y1부터 y1 + L까지 놓입니다. 벽은 격자 밖으로 튀어나올 수 없습니다. 벽은 격자의 바깥 경계선 위에 놓일 수도 있으며, 이 경우 어떤 칸도 나누지 않지만 여전히 올바르게 놓인 벽으로 인정됩니다.

유효한 미로는 다음을 모두 만족해야 합니다.

• 벽 3개를 모두 놓습니다.
• 어떤 두 벽도 서로 교차하지 않습니다. 두 벽이 공유할 수 있는 점은 오직 두 벽 모두의 끝점이 되는 하나의 격자 모서리뿐입니다(길이가 겹치거나, 서로 가로지르거나, 한 벽의 끝이 다른 벽의 중간에 닿는 것은 모두 허용되지 않습니다).
• 모든 벽은 격자 안에 있습니다.

미로가 완성되면 출발 표식이 있는 칸에서 도착 표식이 있는 칸까지의 최단 경로가 정해집니다. 출발 칸과 도착 칸은 서로 다릅니다.

이 문제에서는 반대로, 어떤 미로의 최단 경로가 주어졌을 때 그러한 미로를 만들어야 합니다. 만든 미로는 유효해야 하고, 주어진 경로는 벽을 넘거나 격자 밖으로 나가지 않고 출발 칸에서 도착 칸까지 이어지는 올바른 경로여야 하며, 그보다 더 짧은(이동 횟수가 더 적은) 올바른 경로가 존재해서는 안 됩니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 번째 줄에는 세 벽의 길이를 나타내는 세 개의 양의 정수가 주어집니다(각 길이는 1 이상 6 이하). 두 번째 줄에는 만들려는 미로에서 출발 표식부터 도착 표식까지의 최단 경로를 나타내는, N, E, S, W로 이루어진 길이 1 이상 25 이하의 문자열이 주어집니다. 각 문자는 다음 이동의 방향을 나타냅니다. 각 테스트 케이스는 적어도 하나의 해가 존재함이 보장됩니다.

마지막 테스트 케이스 다음에는 세 개의 0이 적힌 줄이 옵니다.

각 테스트 케이스마다 다섯 줄을 출력합니다.

1. 출발 표식이 있는 칸의 열 번호와 행 번호
2. 도착 표식이 있는 칸의 열 번호와 행 번호 3.~5. 세 벽의 위치(입력에 주어진 길이와 같은 순서로)

각 벽의 위치는 네 정수 x1 y1 x2 y2로 나타냅니다. 가로 벽이면 왼쪽 끝점 다음에 오른쪽 끝점을, 세로 벽이면 위쪽 끝점 다음에 아래쪽 끝점을 적습니다. 각 끝점은 격자 왼쪽 변으로부터의 거리와 위쪽 변으로부터의 거리 순서로 적습니다.

한 테스트 케이스에 유효한 미로가 여러 개 있을 수 있습니다. 그중 사전순으로 가장 작은 미로 하나만 출력합니다. 미로는 그것을 출력할 때 나오는 정수들을 위에서 아래로, 왼쪽에서 오른쪽으로 이어 붙인 수열, 즉 (출발 열, 출발 행, 도착 열, 도착 행, 벽 1의 x1 y1 x2 y2, 벽 2의 값, 벽 3의 값)으로 나타내며, 두 미로는 이 정수 수열을 사전순으로 비교합니다.