Лабиринт — это прямоугольная сетка, каждая из клеток которой либо свободна, либо является стеной, причем перемещаться можно только между смежными по стороне свободными клетками.
Константин и Михаил — мировые лидеры по составлению лабиринтов. Они составили каждый по лабиринту размером n × m, и теперь обвиняют друг друга в плагиате. Они считают, что плагиат имел место, если существует путь из левой верхней клетки в правую нижнюю, являющийся кратчайшим в обоих лабиринтах. Разрешите их спор и скажите, имел ли место плагиат.
В первой строке записаны два числа n и m (1 ≤ n, m ≤ 500) — размеры лабиринтов.
В следующих n строках записан лабиринт, составленный Константином. Каждая из этих n строк состоит из m символов. Каждый из этих символов может быть равен либо «#», что обозначает стену, либо «.», что обозначает свободную клетку.
Следующая строка оставлена пустой, а затем в n строках в аналогичном формате записан лабиринт, составленный Михаилом. Гарантируется, что в обоих лабиринтах левая верхняя и правая нижняя клетки — свободные.
Выведите «YES», если существует путь из левой верхней клетки в правую нижнюю, являющийся кратчайшим в обоих лабиринтах. Иначе выведите «NO».
3 5
.....
.#.#.
.....
.....
#.#.#
.....
NO
3 5
.....
.#.##
.....
.....
##.#.
.....
YES