В магазине мобильных приложений появилась новая игра «Subway Roller».
Главный герой игры Филипп находится в одном конце туннеля и хочет выйти из другого. Туннель представляет собой клетчатое прямоугольное поле, состоящее из трех строк и n столбцов. В начале игры герой находится в некоторой клетке самого левого столбца. Навстречу герою едет некоторое количество поездов. Каждый поезд представляет собой две или более клетки, находящиеся непосредственно друг за другом в некоторой строке поля.
Все поезда двигаются справа налево со скоростью две клетки в секунду, а герой бежит слева направо со скоростью одна клетка в секунду. Для простоты игра реализована так, что герой и поезда двигаются по очереди. Сначала герой двигается на одну клетку вправо, затем на одну клетку вверх или вниз или остается на месте, затем все поезда дважды одновременно перемещаются на одну клетку влево. Таким образом, за один ход Филипп обязательно делает перемещение вправо и может переместиться вверх или вниз. Если в какой-то момент Филипп оказывается в одной клетке с некоторым поездом, то он проигрывает. Если поезд доезжает до левого столбца, то он продолжает двигаться как и ранее, выезжая из туннеля.
Ваша задача ответить на вопрос, существует ли такая последовательность передвижений Филиппа, что он сможет дойти до самого правого столбца.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке слово YES, если пройти игру возможно и слово NO в противном случае.
Примечание
В первом наборе входных данных первого примера Филиппу нужно сначала пройти вперед и спуститься вниз на третью строку поля, затем пройти вперед, затем пройти вперед и подняться на вторую строку, снова пройти вперед и подняться на первую строку. После этого пути Филиппа не преграждает ни один поезд, поэтому он может идти прямо до конца туннеля.
Обратите внимание, что в этой задаче во взломах разрешается использовать только тесты, содержащий один набор входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
16 4
...AAAAA........
s.BBB......CCCCC
........DDDDD...
16 4
...AAAAA........
s.BBB....CCCCC..
.......DDDDD....
|
YES
NO
|
|
2
|
2
10 4
s.ZZ......
.....AAABB
.YYYYYY...
10 4
s.ZZ......
....AAAABB
.YYYYYY...
|
YES
NO
|