가희와 베개

가희는 언니 방에 있는 가방과 베개 위에서 똬리를 틀고 자는 것을 좋아합니다.

[그림 1] 언니 가방 위에 올라와서 똬리를 틀고 있는 가희

가희는 언니가 있는 줄 알고 방에 들어갔지만, 평소와 달리 엄마 주인이 침대 위에 있었습니다. 엄마 주인은 방에 들어온 가희를 내쫓았습니다. 그리고 가희가 언니의 가방과 베개 위에서 자지 못하도록 방에 장애물과 고도 1의 나무토막 여러 개를 설치했습니다.

엄마 주인이 방을 나간 뒤에야 가희는 다시 방에 들어올 수 있었습니다. 그러나 엄마 주인이 설치한 장애물과 나무토막 때문에 가희가 좋아하는 베개와 가방으로 갈 수 없었습니다. 이곳저곳을 돌아다니다 지친 가희는 방의 좌표 (x, y)에서 오빠 주인에게 도움을 요청했습니다. 마침 오빠 주인은 ?로 표시된 곳에 가로 1칸, 세로 1칸을 차지하는 경사로를 설치할 수 있는 장치를 가지고 있었습니다. 가희는 이 장치를 오빠 주인에게 받아, 경사로를 설치할 수 있는 모든 곳에 경사로를 설치한 뒤 베개나 가방이 있는 곳으로 이동하려고 합니다.

경사로가 설치된 방향은 고도가 낮은 쪽에서 높은 쪽으로 올라가는 방향을 뜻합니다. 방향은 북쪽을 나타내는 N, 서쪽을 나타내는 W, 동쪽을 나타내는 E, 남쪽을 나타내는 S 네 가지가 있습니다. 경사로의 방향에 따라 이동할 수 없는 방향도 있습니다. 아래 그림에서 경사로가 설치되지 않은 곳은 고도가 0 또는 1인 곳입니다.

[그림 2-1(왼쪽), 그림 2-2(오른쪽)] 경사로가 설치된 방향과 이동할 수 없는 방향

[그림 2-1]처럼 W 방향이나 E 방향으로 설치된 경사로에서는 위쪽과 아래쪽으로 갈 수 없고, 위쪽이나 아래쪽에서 W 방향이나 E 방향으로 설치된 경사로로 올 수 없습니다. [그림 2-2]처럼 N 방향이나 S 방향으로 설치된 경사로에서는 왼쪽과 오른쪽으로 갈 수 없고, 왼쪽이나 오른쪽에서 N 방향이나 S 방향으로 설치된 경사로로 올 수 없습니다.

[그림 3] 위에서 바라본 경사로의 방향

[그림 3]은 경사로의 방향에 따라 고도가 0인 곳과 1인 곳을 어떻게 잇는지 보여줍니다. [그림 4]를 보겠습니다.

[그림 4] W 방향으로 설치된 경사로를 측면에서 본 모습

좌표 (1, 2)에 W 방향으로 경사로가 설치되었다고 해 봅시다. 이 경우 W 방향 경사로는 고도가 1인 (1, 1)과 고도가 0인 (1, 3)을 잇습니다.

[그림 5] E 방향으로 설치된 경사로를 측면에서 본 모습

반대로 (1, 1)의 고도가 1이고 (1, 3)의 고도가 0이며, (1, 2)에 E 방향으로 경사로가 설치되어 있다면, 가희는 (1, 1)에서 (1, 2)로도, (1, 2)에서 (1, 3)으로도 갈 수 없습니다.

가희는 다음 규칙을 지키며 이동해야 합니다. 그렇지 않으면 무서운 엄마 주인이 가희가 언니 방에 들어왔다는 사실을 눈치챌 것입니다.

• 현재 가희가 있는 곳에서 상하좌우로 인접한 곳으로만 이동할 수 있습니다.
• 벽이 있는 곳으로는 이동할 수 없습니다.
• 고도가 다른 곳으로 이동할 때는 경사로를 통해서만 이동할 수 있습니다.
• 가희는 맵 바깥으로 나갈 수 없습니다.

가희는 오빠 주인이 가져온 장치로 경사로를 설치할 수 있는 모든 곳에 적절한 방향으로 경사로를 설치하려고 합니다. 그렇게 해서 오빠에게 도움을 요청한 곳에서 베개나 가방이 있는 곳까지 갈 수 있게 하려고 합니다. 가희가 목적을 달성하도록 도와주세요.

첫 번째 줄에 언니 방의 세로 길이 $R$과 가로 길이 $C$가 공백으로 구분되어 주어집니다. $R$과 $C$는 1 이상 738 이하의 정수입니다.

두 번째 줄부터 $R$개의 줄에 걸쳐 길이가 $C$인 문자열이 주어집니다. $i$번째 문자열의 $j$번째 문자는 아래 6개 중 하나로, 좌표 (i, j)의 언니 방 정보를 뜻합니다.

• ? : 경사로를 설치할 수 있는 곳
• . : 고도가 0인 곳
• 1 : 고도가 1인 곳(언니 방에 설치된 나무토막 위를 뜻합니다)
• # : 가희가 절대로 갈 수 없는 벽
• P : 베개
• B : 가방

그다음 줄에는 가희가 오빠에게 도움을 요청한 곳의 $x$ 좌표와 $y$ 좌표가 공백으로 구분되어 주어집니다. $x$는 1 이상 $R$ 이하의 정수이며, $y$는 1 이상 $C$ 이하의 정수입니다.

• ?가 표시된 모든 곳에 경사로를 설치해서 가희가 목적을 달성할 수 있다면, 어떤 배치를 출력해도 정답으로 인정합니다.

  • ?가 표시된 모든 곳에는 'N', 'W', 'E', 'S' 중 하나가 있어야 합니다.
  • 그 외의 곳은 바꾸면 안 됩니다. 예를 들어 벽이 있던 곳의 벽을 없애 고도를 1로 만드는 것은 허용되지 않습니다.

• ?가 표시된 모든 곳에 어떤 방법으로 경사로를 설치해도 목적을 달성할 수 없다면 -1을 출력하세요.

• 경사로를 설치할 수 있는 곳의 고도는 0입니다.
• 베개와 가방이 있는 곳의 고도는 0입니다.
• 가희가 현재 있는 곳인 좌표 (x, y)에는 '#'이나 '?'가 없습니다.
• '?'(설치할 수 있는 경사로)의 개수는 0 이상 18 이하입니다.
• 경사로를 설치할 수 있는 곳들은 서로 인접하지 않습니다.