Gahee and the Pillow

Gahee likes to curl up and sleep on the bags and pillows in her older sister's room.

[Figure 1] Gahee curled up on the sister's bag

Gahee walked into the room thinking her sister was inside, but Mom was on the bed instead. Mom chased Gahee out and placed obstacles and several wooden blocks of height 1 in the room so Gahee could not sleep on the sister's bag and pillows.

Only after Mom left the room could Gahee come back in. The obstacles and blocks Mom had placed kept Gahee from reaching the pillows and bags. After wandering around for a while, Gahee asked the older brother for help at the coordinates (x, y) in the room. The brother had a device that can build a ramp covering 1 cell by 1 cell in each cell marked with ?. Gahee takes the device from the brother and builds ramps in every place where a ramp can be built. Then Gahee moves to the pillow or the bag.

A ramp's direction is the direction in which the ground rises from low to high. There are four directions: N for north, W for west, E for east, and S for south. Depending on the direction of the ramp, some moves are blocked. In the figure below, the cells without a ramp have height 0 or 1.

[Figure 2-1 (left), Figure 2-2 (right)] Ramp directions and blocked moves

As in [Figure 2-1], a ramp facing W or E blocks movement up and down from it, and blocks movement into it from above and below. As in [Figure 2-2], a ramp facing N or S blocks movement left and right from it, and blocks movement into it from the left and right.

[Figure 3] Ramp directions seen from above

[Figure 3] shows how a ramp with a given direction connects a cell of height 0 to a cell of height 1. Look at [Figure 4].

[Figure 4] A ramp facing W, seen from the side

Suppose a ramp facing W is built at (1, 2). Then this ramp connects (1, 1), which has height 1, with (1, 3), which has height 0.

[Figure 5] A ramp facing E, seen from the side

Now suppose (1, 1) has height 1, (1, 3) has height 0, and a ramp facing E is built at (1, 2). Gahee cannot move from (1, 1) to (1, 2), and cannot move from (1, 2) to (1, 3).

Gahee must follow these rules while moving. Otherwise, the frightening Mom will notice that Gahee entered the sister's room.

• Gahee can move only to an adjacent cell up, down, left, or right.
• Gahee cannot move into a cell with a wall.
• When moving to a cell at a different height, Gahee can move only through a ramp.
• Gahee cannot leave the map.

Gahee uses the device from the older brother to build a ramp in every place where a ramp can be built, each in a suitable direction. In this way, Gahee wants to reach the pillow or the bag from the place where Gahee asked the brother for help. Please help Gahee reach the goal.

The first line contains the number of rows $R$ and the number of columns $C$, separated by a space. Both $R$ and $C$ are integers from 1 to 738.

The next $R$ lines each contain a string of length $C$. The $j$-th character of the $i$-th string is one of the six characters below, which describes the room at coordinates (i, j).

• ? : a cell where a ramp can be built
• . : a cell of height 0
• 1 : a cell of height 1 (on top of a wooden block placed in the room)
• # : a wall that Gahee can never enter
• P : a pillow
• B : a bag

The last line contains the x and y coordinates of the place where Gahee asked the brother for help, separated by a space. $x$ is an integer from 1 to $R$, and $y$ is an integer from 1 to $C$.

• If you can build ramps in every ? cell so that Gahee reaches a pillow or a bag, print any valid arrangement.

  • Each ? cell must contain one of 'N', 'W', 'E', or 'S'.
  • Other cells must not be changed. For example, you cannot remove a wall to make its height 1.

• If no way of building ramps in all ? cells lets Gahee reach a pillow or a bag, print -1.

• The height of each cell where a ramp can be built is 0.
• The height of each cell with a pillow or a bag is 0.
• The cell (x, y) where Gahee is standing has no # and no ?.
• The number of ? cells is at least 0 and at most 18.
• No two cells where a ramp can be built are adjacent.