P17376 [ECNA 2023] Pearls

谜题镇的 Nikoli 珠宝店出售一系列由黑珍珠和白珍珠组成的项链。珍珠被牢牢粘在一根长度为 $k$ 的绳子上；绳子的每个单位长度上要么有一颗珍珠，要么是一段空绳。 每条项链都陈列在一块铺有天鹅绒的矩形网格上。网格中的每个单元格要么放置一颗珍珠，要么容纳一个单位长度的空绳，要么既没有珍珠也没有绳子。绳子的每一段都沿水平方向或竖直方向放置。一条正确陈列的项链对应一条连接若干网格单元、封闭且不自交的路径。 这里毕竟是谜题镇，因此 Nikoli 为项链的陈列制定了一些巧妙的规则，也就是名为 Masyu 的谜题规则。当项链沿路径放置时，绳子上的单位间距与陈列网格的单元间距相同，珍珠必须满足下列约束： - 白珍珠不能放在路径转弯的单元格中；此外，路径穿过白珍珠后向两侧延伸所到达的两个相邻单元格中，至少有一个必须发生转弯。 - 黑珍珠必须放在路径转弯的单元格中；此外，路径从黑珍珠向两侧延伸所到达的两个相邻单元格都不能发生转弯。 图 1 展示了一条正确陈列的项链，它也对应样例输入 1。 Nikoli 的顾客有些挑剔，因此他又对项链增加了三条限制： - 项链长度中至少有一半的位置放有珍珠，而不是空绳； - 黑珍珠更受欢迎——至少价格更高——所以富有的谜题镇居民坚持要求黑珍珠数量至少是白珍珠数量的两倍； - 任意两颗相邻珍珠之间的空绳长度都不超过五个单位。 Nikoli 有时会发现，即使已经按照这些限制制作好项链，也无法依照上述规则将它陈列出来。请帮助他！ :::align{center}  :::

第一行包含三个整数 $k,n,m$。其中 $k$ 是绳子的长度，满足 $5\le k\le 60$；$n,m$ 分别是天鹅绒网格的行数和列数，满足 $5\le n,m\le 50$。左上角单元格为第 $1$ 行第 $1$ 列。 第二行包含一个长度为 $k$ 的字符串，只由字符 `B`、`W` 和 `.` 组成，分别表示黑珍珠、白珍珠和一单位长的空绳。第一个字符一定表示珍珠，即为 `B` 或 `W`。 第三行包含两个整数 $r,c$，表示字符串中第一颗珍珠所在网格的行号与列号，其中 $1\le r\le n$，$1\le c\le m$。

如果能在给定网格边界内正确陈列项链，则输出描述项链布局的路径字符串。假定输入字符串中的第一颗珍珠位于网格第 $r$ 行第 $c$ 列，并且路径必须按照输入字符串的顺序依次经过其中的珍珠与空绳位置。 路径字符串仅由字母 `N`、`S`、`E`、`W` 组成，分别表示从当前单元格向北、南、东、西前进一步。路径必须封闭且不能与自身相交。如果有多条符合条件的路径，输出描述字符串中字典序最小的一条。 如果不存在满足 Masyu 约束的路径，输出 `impossible`。