← 返回题目列表

Codeforces · 607/C

C. 弹珠

中文机器翻译题面 查看原题

本着节日的精神,埼玉给了杰诺斯两条长度为 n 的网格路径(即使按照埼玉的标准,这也是一个奇怪的礼物)。网格路径是无限网格中相邻方块的有序序列。如果两个正方形共享一条边,则它们是相邻的。

网格路径的一个示例是 (0, 0) → (0, 1) → (0, 2) → (1, 2) → (1, 1) → (0, 1) → ( - 1, 1)。请注意,此序列中的方块可能会重复,即路径具有自交点。

网格路径内的移动仅限于序列内的相邻方块。也就是说,从第i个方格开始,只能移动到该路径的第(i-1)个或第(i+1)个方格。请注意,网格路径的第一个和最后一个方格中只有一个有效的移动。另请注意,即使路径中有某个第 j 个方格与第 i 个方格重合,也只能移动到第 (i - 1) 个方格和第 (i + 1) 个方格。例如,从上述序列中的第二个方格开始,只能移动到第一个或第三个方格。

为了确保移动不含糊,两条网格路径不会有三个方块的交替序列。例如,连续的子序列 (0, 0) → (0, 1) → (0, 0) 不能出现在有效的网格路径中。

一个弹珠被放置在每个网格路径的第一个方格上。杰诺斯想让两个弹珠都到达每个网格路径的最后一个方格。然而,有一个问题。每当他移动一颗弹珠时,如果可能的话,另一颗弹珠就会复制它的移动。例如,如果一个弹珠向东移动,那么另一颗弹珠也会尝试向东移动。通过尝试,我们的意思是,如果向东移动是有效的移动,那么弹珠就会向东移动。

向北移动第二个坐标增加 1,向南移动则减少 1。同样,向东移动第一个坐标增加 1,而向西移动则减少。

给定这两条有效的网格路径,杰诺斯想知道是否可以将两个弹珠移动到各自路径的末端。也就是说,是否可以移动弹珠,使得两个弹珠都停留在它们各自路径的最后一个方格上。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 1 000 000) — 路径的长度。

输入的第二行包含一个由 n - 1 个字符组成的字符串(每个字符为“N”、“E”、“S”或“W”)——第一个网格路径。角色可以被认为是穿过网格路径所需的移动序列。例如,问题陈述中的示例路径可以用字符串“NNESWW”表示。

输入的第三行包含 n - 1 个字符的字符串(每个字符为“N”、“E”、“S”或“W”)——第二个网格路径。

输出

如果两个弹珠有可能同时到达结束位置,则打印“YES”(不带引号)。否则打印“NO”(不带引号)。在这两种情况下,答案都不区分大小写。

示例

输入 #1

7
NNESWW
SWSWSW

输出 #1

YES

输入 #2

3
NN
SS

输出 #2

NO

注意

在第一个示例中,第一个网格路径是语句中描述的路径。此外,以下移动顺序将使两个弹珠都到达终点:NNESWWSWSW。

在第二个示例中,没有任何移动序列可以让两个弹珠都到达终点。