Dabi 是一位享誉银河系的冒险家，她进入了一座被遗忘已久的地下城，据说那里隐藏着古代宝藏。在漆黑的隧道中，她必须在城市崩塌前找到一把钥匙并抵达宝藏箱所在的位置。
整个城市可以表示为一个 $h \times w$ 的网格（$3 \le h, w \le 16$）。网格中的每个单元格属于以下类型之一： 空单元格：可通行的通道。 墙壁单元格：不可进入的实体块。 *传送单元格：一种连接两个遥远地点的古代装置。
关于这座地下城，已知以下事实： 网格边界上的所有单元格（即最顶行/最底行，或最左列/最右列）均为墙壁。 所有墙壁单元格通过四个方向（北、南、东、西）相连，即它们构成一个单一的 4 连通分量。 所有空单元格相连，构成一个被墙壁包围的单一 4 连通分量。 对于每个传送单元格，其周围的八个邻近单元格均为空间单元格。 每个传送单元格恰好属于一个传送对。如果 Dabi 从任何方向进入一个传送单元格，她会立即被传送到其配对的单元格，并沿着进入传送单元格时的相同方向额外移动一步。此过程不会触发另一次传送。 每个传送对用大写字母 A、B、C、D、E 或 F 标记。因此，总共最多有 $6 \times 2 = 12$ 个传送单元格。 * 恰好有一把钥匙和一个宝藏箱，分别放置在不同的空单元格上，且都不在 Dabi 的初始位置。
图 1. 地下城的一个示例配置（$h = 7; w = 9$），包含两对传送门 A 和 B。
Dabi 可以执行以下两种动作： 移动到四个相邻单元格中非墙壁的单元格。传送以及随后的额外移动被视为“进入传送单元格”的一部分，不计为单独的动作。 如果她位于钥匙所在的单元格，则拾取钥匙。
Dabi 在每次动作前后始终站在空单元格上。
图 1 展示了一个 $h = 7$ 且 $w = 9$ 的地下城示例。传送对 A 连接了两个标记为 A 的单元格，传送对 B 连接了两个标记为 B 的单元格。注意，图 1 对应于随附的 sample.in 文件中描述的城市。
如图 2 所示，传送过程如下。在图 2(a) 中，Dabi 站在传送门 A 东侧的单元格上。当她向西移动时，她进入了标记为 A 的传送单元格，立即被传送到其配对单元格，然后向西额外移动一步，结果如图 2(b) 所示。
图 2. 传送过程示意图。(a) Dabi 站在传送门 A 东侧的单元格上。(b) 向西移动后，她进入传送单元格 A，被传送到配对单元格，并向西额外移动一步。
当 Dabi 拾取钥匙时，城市开始崩塌。从那一刻起，她必须以最少的动作次数到达宝藏单元格。任何更长的路径都会导致尝试失败。
Dabi 携带一个可靠的指南针，总是能分辨北、南、东、西。通过感知周围的墙壁，她可以判断四个方向中每个方向的相邻单元格是否为墙壁。然而，她最初并不知道自己的坐标或城市的整体布局。在任何时刻，她还可以感知当前单元格是否包含钥匙或宝藏。她可以站在钥匙所在的单元格上而不立即拾取它。
你的任务是引导 Dabi 穿过城市以获得钥匙，然后到达宝藏箱，并遵守所有移动规则。编写一个程序，通过与交互器进行一系列命令交互来完成此任务。
交互
这是一个交互式问题。你提交的程序将与评测服务器内的交互器进行交互，交互器从你的程序读取输入并向其写入输出。你的程序必须通过打印命令并读取交互器的回复来控制 Dabi。每次输出一行后，必须立即刷新输出。
输入格式
在交互开始时，交互器提供有关 Dabi 当前单元格的信息。信息以单行形式给出，包含六个字符，中间没有空格： 这六个字符中的每一个都是 '0' 或 '1'。 前四个字符中，'1' 表示该方向的相邻单元格是墙壁，'0' 表示不是墙壁。方向顺序为北、南、东、西。 第五个字符：如果当前单元格有钥匙且尚未被拾取，则为 '1'；否则为 '0'。 第六个字符：如果宝藏箱在当前单元格，则为 '1'；否则为 '0'。 * 由于钥匙和宝藏箱位于不同的单元格，第五个和第六个字符不会同时为 '1'。
例如，“100010”表示北面有墙，其他三个方向畅通，当前单元格有未拾取的钥匙，且没有宝藏。
命令
你的程序可以重复输出以下命令之一，直到交互器输出“correct”或终止交互。
- “N”、“S”、“E”或“W”
- 向选定方向移动一步——“N”（北）、“S”（南）、“E”（东）或“W”（西）。目标单元格不能是墙壁。如果是传送单元格，Dabi 将按照上述规则进行传送。
- 尝试移动到墙壁会导致交互器输出“wrong”。
- “K”
- 拾取当前单元格上的钥匙。此动作后，宝藏箱打开，从那一刻起，Dabi 必须以最少的动作次数到达宝藏单元格。
- 如果当前单元格没有未拾取的钥匙，交互器输出“wrong”。
每个命令必须打印在单独的一行上并立即刷新。发出的命令总数不得超过 230,611。
交互器响应
每次动作后，交互器响应如下： 如果 Dabi 已经拾取了钥匙，并且刚刚以最少的动作次数到达了宝藏单元格，交互器输出“correct”。 如果违反了任何规则，交互器会立即终止交互——例如，命令格式错误、无效移动、尝试拾取不存在或已拾取的钥匙、总动作次数超过 230,611，或者在拾取钥匙后通过非最短路径到达宝藏。 * 否则，交互器输出一个六字符字符串，描述 Dabi 的新当前单元格，格式与初始输入相同。
收到“correct”意味着你的程序已成功完成任务，应优雅地终止。打印每个命令后，请务必刷新输出。
城市布局在整个交互过程中是固定的；交互器不是自适应的。
交互器使用的时间和内存也包含在你的程序执行时间和内存使用量的计算中。你可以假设交互器使用的最大时间为 1 秒，最大内存为 64 MiB。
样例
输入 1
101000
输出 1
W
输入 2
000000
输出 2
W
输入 3
000000
输出 3
S
输入 4
010000
输出 4
W
输入 5
010110
输出 5
K
输入 6
010100
输出 6
N
输入 7
000000
输出 7
W
输入 8
010100
输出 8
N
输入 9
000100
输出 9
E
输入 10
correct
说明
要刷新输出，你需要在写入命令和换行符后执行以下操作：
C 语言中使用 fflush(stdout)；
C++ 中使用 std::cout << std::flush；
Java 或 Kotlin 中使用 System.out.flush()；
Python 中使用 sys.stdout.flush()。
提供了一个测试工具来帮助你开发解决方案，使用它不是强制性的。如果你想使用它，可以从 DOMjudge 问题集页面下载附件 testing_tool.py。你可以运行该测试工具来查看你的程序在特定城市布局下的交互方式。无论你的程序使用何种语言，都可以按以下方式使用此测试工具。同样的说明也包含在 testing_tool.py 的注释中。
用法：python3 testing_tool.py -f <inputfile> <program>
使用 -f 参数指定输入文件，例如 input.in。
输入文件格式：第一行包含两个整数 $h$ 和 $w$。接下来的 $h$ 行，每行包含一个长度为 $w$ 的字符串，描述城市地图。每个字符代表的单元格类型如下： ‘#’：墙壁单元格。 ‘.’：空单元格。 ‘k’：包含钥匙的空单元格。 ‘t’：包含宝藏箱的空单元格。 ‘v’：Dabi 最初站立的空单元格。 ‘A’、‘B’、‘C’、‘D’、‘E’、‘F’：传送单元格，每个字母代表一个传送对。
示例：图 1 所示的城市表示如下。
7 9 ######### ###...### #...A.v## #.B.....# #...A.Bt# ##k.....# #########
该工具按原样提供，你可以随意进行修改或扩充。请注意，通过测试工具的程序并不保证一定会被接受。例如，测试工具不会验证 Dabi 在拾取钥匙后是否以最少的动作次数到达宝藏箱；它只会报告执行了多少次动作。