| Codeforces Round 325 (Div. 1) |
|---|
| Закончено |
В магазине мобильных приложений появилась новая игра «Subway Roller».
Главный герой игры Филипп находится в одном конце туннеля и хочет выйти из другого. Туннель представляет собой клетчатое прямоугольное поле, состоящее из трех строк и n столбцов. В начале игры герой находится в некоторой клетке самого левого столбца. Навстречу герою едет некоторое количество поездов. Каждый поезд представляет собой две или более клетки, находящиеся непосредственно друг за другом в некоторой строке поля.
Все поезда двигаются справа налево со скоростью две клетки в секунду, а герой бежит слева направо со скоростью одна клетка в секунду. Для простоты игра реализована так, что герой и поезда двигаются по очереди. Сначала герой двигается на одну клетку вправо, затем на одну клетку вверх или вниз или остается на месте, затем все поезда дважды одновременно перемещаются на одну клетку влево. Таким образом, за один ход Филипп обязательно делает перемещение вправо и может переместиться вверх или вниз. Если в какой-то момент Филипп оказывается в одной клетке с некоторым поездом, то он проигрывает. Если поезд доезжает до левого столбца, то он продолжает двигаться как и ранее, выезжая из туннеля.
Ваша задача ответить на вопрос, существует ли такая последовательность передвижений Филиппа, что он сможет дойти до самого правого столбца.
Каждый тест содержит от одного до десяти наборов входных данных. В первой строке теста находится одно целое число t (1 ≤ t ≤ 10 для претестов и тестов, t = 1 для взломов; смотрите в секцию Notes для пояснения) — количество наборов.
Далее следует описание t наборов входных данных.
В первой строке описания каждого набора находятся два целых числа n, k (2 ≤ n ≤ 100, 1 ≤ k ≤ 26) — количество столбцов на поле и количество поездов. В каждой из следующих трех строк находится последовательность из n символов, представляющих собой строку поля, на котором проходит игра. Начальное положение Филиппа обозначено символом 's' и находится в самом левом столбце. Каждый из k поездов обозначен некоторой последовательностью подряд идущих одинаковых прописных букв английского алфавита, находящихся в одной строке. Различные поезда обозначены различными буквами. Символ '.' обозначает пустую клетку, то есть клетку без Филиппа и поездов.
Для каждого набора входных данных выведите в отдельной строке слово YES, если пройти игру возможно и слово NO в противном случае.
2
16 4
...AAAAA........
s.BBB......CCCCC
........DDDDD...
16 4
...AAAAA........
s.BBB....CCCCC..
.......DDDDD....
YES
NO
2
10 4
s.ZZ......
.....AAABB
.YYYYYY...
10 4
s.ZZ......
....AAAABB
.YYYYYY...
YES
NO
В первом наборе входных данных первого примера Филиппу нужно сначала пройти вперед и спуститься вниз на третью строку поля, затем пройти вперед, затем пройти вперед и подняться на вторую строку, снова пройти вперед и подняться на первую строку. После этого пути Филиппа не преграждает ни один поезд, поэтому он может идти прямо до конца туннеля.
Обратите внимание, что в этой задаче во взломах разрешается использовать только тесты, содержащий один набор входных данных.
