题目描述

由于牛奶市场的萧条，奶牛们不得不搬到城市里谋生。唯一能找到的工作就是当出租车司机。请帮助奶牛熟悉城市路线。

已知一张城市地图，有 $E$（$1 \leq E \leq 40$）条东西方向的街道坐标和 $N$（$1 \leq N \leq 30$）条南北方向的街道坐标。请为出租车司机生成一套从起点 $S$ 到终点 $E$ 的最短路径导航指令。

每条指令包括一个方向（N, E, S, W）和一个整数，表示应沿该方向行驶多少个街区。若有多条路线可选，保证最短路线是唯一的。

地图由如下元素组成：

'+'：表示街道交叉点；

'-'、'|'：分别表示东西、南北方向可以通行的道路；

'.'：表示建筑或障碍，不可通行；

'S'：起点；

'E'：终点。

示例地图：

+-+-+.+-+-+
|...|.....|
+-+.+-+-+-+
..|.......|
S-+-+-+.E-+

输入格式

第 1 行：两个整数 $N$ 和 $E$，表示南北与东西方向的街道数；

第 $2$ 到 $2N+1$ 行：每行为 $2E - 1$ 个字符，奇数行为东西方向的街道，偶数行为东西方向之间的道路（垂直）。

输出格式

每行一个指令，格式为：<方向> <步数>，按路径顺序输出。

3 6
+-+-+.+-+-+
|...|.....|
+-+.+-+-+-+
..|.......|
S-+-+-+.E-+

E 1
N 1
W 1
N 1
E 2
S 1
E 3
S 1
W 1