你拥有两个机器人，它们分别位于两个独立的矩形迷宫中。迷宫中的方格 $(1, 1)$ 是左上角的方格，即西北角。迷宫 $i$ ($i = 1, 2$) 有 $G_i$ ($0 \le G_i \le 10$) 个守卫，他们在一条直线的巡逻路径上往返巡逻，试图捕获机器人。你的目标是确定一个指令序列，使得两个机器人都能走出迷宫，且在此过程中没有任何一个机器人被守卫捕获。
在每分钟开始时，你向两个机器人广播相同的指令。每个指令是一个方向（北、南、东或西）。机器人会沿着指令的方向移动一个方格，除非它会撞到墙壁，在这种情况下，机器人该分钟内不移动。机器人通过走出迷宫边界来离开迷宫。机器人走出迷宫后将忽略后续的指令。
守卫在每分钟开始时移动一个方格，与机器人同时移动。每个守卫从给定的方格开始，面向给定的方向，每分钟向前移动一个方格，直到移动的步数比其巡逻路径上的方格数少 $1$。随后，守卫会立即转身，沿相反方向走回其起点，在起点再次转身，并重复其巡逻路径，直到所有机器人均已走出迷宫。
守卫的巡逻不会要求其穿过墙壁或走出迷宫。尽管守卫的巡逻路径可能会重叠，但任意两个守卫绝不会相撞：他们绝不会在某一分钟结束时占用同一个方格，也不会在某一分钟内相互交换位置。迷宫中的守卫不会与该迷宫中的机器人从同一个方格开始。
如果守卫和机器人在某一分钟结束时占用了同一个方格，或者守卫和机器人在某一分钟内相互交换了位置，则视为守卫捕获了机器人。
给定两个迷宫（每个大小不超过 $20 \times 20$）、每个机器人的初始方格以及每个迷宫中守卫的巡逻路径，确定一个指令序列，使机器人在不被守卫捕获的情况下走出迷宫。你需要最小化较晚走出迷宫的机器人所花费的时间。如果两个机器人走出迷宫的时间不同，较早走出的机器人的具体退出时间并不重要。
输入格式
第一组行描述第一个迷宫及其中的角色。随后，第二组行描述第二个迷宫及其中的角色。
- 输入的第一行包含两个空格分隔的整数 $R_1$ 和 $C_1$，表示迷宫 1 的行数和列数。
- 接下来的 $R_1$ 行每行包含 $C_1$ 个字符，指定迷宫的布局。机器人的起始方格用
'X'表示，'.'表示空地，'#'表示墙壁。每个迷宫将恰好包含一个机器人。 - 紧随迷宫布局之后的是单行，包含一个整数 $G_1$，表示第一个迷宫中的守卫数量（$0 \le G_1 \le 10$）。
- 接下来的 $G_1$ 行中，每行描述一个守卫的巡逻路径，包含三个整数和一个字符，用单个空格分隔。前两个整数指定守卫起始方格的行和列。第三个整数指定守卫巡逻路径中的方格数（$2 \dots 4$）。字符指定守卫初始面向的方向：分别为
'N'（北）、'S'（南）、'E'（东）或'W'（西）。
第二个迷宫的描述紧随第一个迷宫之后，格式相同，但数值可能不同。
输出格式
输出的第一行应包含一个整数 $K$ ($K \le 10000$)，表示使两个机器人均在不被捕获的情况下走出迷宫所需的指令数。如果存在这样的指令序列，则最短的序列将不超过 $10000$ 条指令。
接下来的 $K$ 行是指令序列，每行包含集合 {'N', 'S', 'E', 'W'} 中的一个字符。如果不存在这样的序列，则输出单行 "-1"。
在指令结束时，两个机器人均应走出各自的迷宫。最后一条指令应使至少一个机器人走出其迷宫。如果有多条指令序列能使机器人在最短时间内走出迷宫，接受其中任意一条。
样例
输入样例 1
5 4 #### #X.# #..# ...# ##.# 1 4 3 2 W 4 4 #### #... #X.# #### 0
输出样例 1
8 E N E S S S E S
评分方式
对于不存在可行指令序列的测试用例，不给部分分。对于其他测试用例，将按如下所述给予部分分：
- 正确性：20% 的分数。如果测试用例的输出文件格式正确、包含不超过 $10000$ 条指令，且该指令序列能使机器人走出迷宫，且最后一条指令使至少一个机器人走出其迷宫，则获得该部分分数。
- 极小性：80% 的分数。如果测试用例的输出文件正确，且不存在更短的正确指令序列，则获得该部分分数。如果程序的指令序列不是极小的，则无法获得极小性的分数。