旋转企鹅迷宫

有时我需要尽可能快地引导一只企鹅穿过迷宫，以便它能找到藏在里面的鱼。我已经教会了企鹅熟练使用指南针，因此可以给它下达 'E'（东）、'N'（北）、'W'（西）和 'S'（南）的指令。企鹅的迷宫还有一个额外特征：某些地块上设有压力板，当企鹅踩上去时，迷宫所在的整个冰山会发生 90 度逆时针旋转。企鹅对此一无所知，因为它会随冰山一起旋转。然而，指南针的指针不会随冰山旋转，因此每当压力板被触发时，我都必须修改我的指令。长此以往，这会让我头疼，所以请你写一个程序来帮我解决这个问题。

幸运的是，从起点到终点始终只有一条路径。任意两个地块之间都存在唯一路径，且起点地块永远不会包含压力板。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例的第一行包含两个整数 $X$ 和 $Y$，表示迷宫在 $X$ 和 $Y$ 方向上的大小；第二行包含 4 个整数 $px, py, gx, gy$，分别表示企鹅的起始坐标和目标地块坐标。接下来有 $Y$ 行，每行包含 $X$ 个字符，其中每个字符代表迷宫的一个地块，以 32 进制数（$0, 1, \dots, 9, A, B, \dots, V$）表示。该数值是地块所包含特征的总和：如果地块有向东的通道，则总和加 1；如果有向北的通道，则加 2；向西的通道加 4；向南的通道加 8。此外，如果地块包含压力板，则加 16（或 G）。因此，例如地块值为 H（或 17）表示该地块有向东的通道且有一个压力板。

输出格式

对于每个测试用例，输出一行指南针指令，引导企鹅沿最短路径到达藏有鱼的地块，假设每条指令都会使企鹅在给定方向上移动恰好一个地块。

Notes and Constraints

$0 < T \le 100$
$0 < X \le 500$
$0 < Y \le 500$
$0 \le px, gx < X$
$0 \le py, gy < Y$

样例

输入格式 1

输出格式 1

ESE

QOJ.ac

QOJ

#3384. 旋转企鹅迷宫