装载机在仓库中工作,仓库是一块大小为 n × m 的矩形场地。该场地的一些牢房是空闲的,其他的则被柱子占据,仓库的屋顶就靠在柱子上。
其中一个空闲单元中有负载,另一个空闲单元中有加载器。任何时候,装载机和货物都不能位于有立柱的单元内、仓库外或同一单元内。
装载机可以移动到相邻的单元(如果两个单元具有公共边,则认为它们是相邻的),或者移动负载。要移动负载,装载机应到达负载附近的单元并推动负载。在这种情况下,负载沿着装载机推动的方向前进到下一个单元,并且装载机最终到达负载所在的单元。
您的任务是确定一系列推动和装载机的移动,之后负载将到达给定的单元(保证该单元是空闲的)。负载相当重,因此您需要首先尽量减少推动次数,其次减少装载机的移动次数。
输入
第一行包含两个正整数 n 和 m (1 ≤ n, m ≤ 40, n·m ≥ 3) — 矩形字段中的行数和列数。
接下来的 n 行每行包含 m 个字符——仓库的描述。如果仓库的下一个单元格中有一个字符:
- “X”,表示当前单元格包含该列;
- “.”,表示当前单元格空闲;
- “Y”,表示加载程序在当前单元格中;
- “B”,表示负载在当前单元格;
- “T”,这意味着负载应该移动到这个单元格。
保证恰好有一个负载、一个装载机和一个负载应移动到的单元。
输出
如果装载机无法将负载移动到给定的单元格,请在输出的第一行打印“NO”(不带引号)。
否则,在输出的第一行和第二行中打印“YES”(不带引号)——确定加载程序的移动和推动的字符序列。字符w、e、n、s分别表示装载机向西、东、北、南移动。字符 W、E、N、S 必须表示装载机在相应方向上的推动。首先,您需要最大限度地减少负载的推动次数,其次是装载机的移动次数。如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
3 3 ..Y .BX ..T
输出 #1
YES wSwsE
输入 #2
3 3 .BY ... TXX
输出 #2
NO