Problem J

Nikoli’s Jewelry Store in Puzzletown sells a line of necklaces consisting of black and white pearls. The pearls in the necklace are firmly glued to a cord of length $k$, where each unit of cord length either holds a pearl or is empty. Each necklace is displayed on a rectangular velvet-lined surface divided into a grid, where each cell of the grid either holds a pearl, or contains a unit of empty cord, or is unoccupied by either pearl or cord. All cord sections are either horizontal or vertical. A properly-displayed necklace corresponds to a closed, non-self-intersecting path connecting some of the cells of the display.

Because this is, after all, Puzzletown, Nikoli uses some tricky rules governing how the necklace is to be displayed, namely, the rules of a puzzle called “Masyu.” When the the necklace is set down along the path (the spacing units on the string match the spacing of the cells on the display surface), the pearls satisfy the constraints of the Masyu puzzle, i.e.,

  • A white pearl may not be set down on a cell containing a path corner; in addition, at least one of the two adjacent cells that extend the path through the pearl must contain a corner.

  • A black pearl must be placed in a cell containing a path corner; in addition, neither of the two cells extending the path through the black pearl may contain a corner.

An example of a necklace correctly displayed is shown in Figure 1 (this also corresponds to sample input 1).

\includegraphics[width=.5\textwidth ]{figure1-new.png}
Figure 1: A necklace of length 16 on its display platform

Nikoli’s clientele are somewhat picky, so he places three further restrictions on his necklaces. At least half of the necklace’s length consists of pearls rather than empty sections of cord. And because black pearls are more desirable (or at least, more expensive) than white ones, the wealthy residents of Puzzletown insist that there be at least twice as many black pearls as white ones. Finally, no two pearls are ever separated by a gap of empty cord longer than five units.

Nikoli sometimes finds that once he has created a necklace according to these restrictions, he is not able to display it according to the rules above. Please help him!


The first line contains $3$ integers $k$, $n$, and $m$, where $k$ ($5 \leq k \leq 60$) is the length of the cord and $n$ and $m$ ($ 5 \leq n,m \leq 50$) are respectively the number of rows and columns of the velvet grid. The upper-left cell is row $1$, column $1$. The second line contains a string of length $k$ consisting only of the characters ‘B’, ‘W’, and ‘.’ (for black pearl, white pearl, and empty cord segment). The first character will always be a pearl—either B or W. The third line contains two integers $r$ and $c$ ($1 \leq r \leq n$, $1 \leq c \leq m$), the row and column of the grid that contains the first pearl in the string.


If there exists a proper way to display the necklace within the given grid boundaries, print a path description of the necklace layout, assuming the first pearl in the string is located at row $r$, column $c$ of the grid and the path describes the pearls and empty spaces in the same sequence as the input string. The path description should consist of the letters N,S,E, and W, indicating whether the path proceeds north, south, east, or west from the current cell. The path should be closed and should not intersect itself. If there is more than one such path, output the one whose description is alphabetically the smallest.

If there is no possible path satisfying the Masyu constraints, output impossible

Sample Input 1 Sample Output 1
16 5 6
3 1
Sample Input 2 Sample Output 2
6 5 5
3 3

Please log in to submit a solution to this problem

Log in