← 返回题目列表

Codeforces · 198/B

B. 在墙上跳

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

Vasya 与忍者一起玩电脑游戏。在这个阶段,瓦夏的忍者应该走出深深的峡谷。

峡谷由两个垂直平行的墙壁组成,它们的高度为n米。想象一下,我们将这些墙分成 1 米长的区域,并从下到上用 1 到 n 的正整数进行编号。有些区域是安全的,忍者可以攀爬它们。其他人都是尖尖的,忍者不可能在那里。我们称这些区域为危险区域。

最初,忍者位于左墙的下部区域。他可以利用每一秒来执行以下操作之一:

- 向上爬一个区域;
- 向下爬一个区域;
- 跳到对面的墙上。这会让忍者到达比他跳下的区域高 k 米的区域。更正式地说,如果在跳跃之前忍者位于一面墙的 x 区域,那么跳跃之后他位于另一堵墙的 x + k 区域。

如果在某个时间点忍者试图到达数字大于 n 的区域,那么我们可以假设忍者已经离开峡谷。

峡谷被洪水淹没,水位每秒上升一米。最初,水位位于第一区域的下边界。忍者不能出现在被水覆盖的区域。我们可以假设忍者和水“轮流移动”——首先忍者执行一些动作,然后水上升一米,然后忍者再执行一个动作,依此类推。

如果忍者设法离开峡谷,则认为该关卡已完成。

在几次失败的尝试之后,Vasya 开始怀疑是否有可能完成这个关卡。帮他回答问题。

输入

第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 105) — 对应峡谷的高度和忍者跳跃的高度。

第二行包含对左墙的描述——一个长度为n个字符的字符串。第i个字符代表第i个墙区域的状态:字符“X”代表危险区域,字符“-”代表安全区域。

第三行以相同的格式描述了右墙。

保证左墙第一个区域不危险。

输出

如果忍者可以离开峡谷,则打印“YES”(不带引号),否则,打印“NO”(不带引号)。

示例

输入 #1

7 3
---X--X
-X--XX-

输出 #1

YES

输入 #2

6 2
--X-X-
X--XX-

输出 #2

NO

注意

在第一个示例中,忍者应该首先跳到右墙,然后沿着右墙向下一米,然后跳到左墙。下一跳就可以把忍者从峡谷中救出来。

在第二个示例中,忍者无法离开峡谷。