The mobile application store has a new game called "Subway Roller".

The protagonist of the game Philip is located in one end of the tunnel and wants to get out of the other one. The tunnel is a rectangular field consisting of three rows and n columns. At the beginning of the game the hero is in some cell of the leftmost column. Some number of trains rides towards the hero. Each train consists of two or more neighbouring cells in some row of the field.

All trains are moving from right to left at a speed of two cells per second, and the hero runs from left to right at the speed of one cell per second. For simplicity, the game is implemented so that the hero and the trains move in turns. First, the hero moves one cell to the right, then one square up or down, or stays idle. Then all the trains move twice simultaneously one cell to the left. Thus, in one move, Philip definitely makes a move to the right and can move up or down. If at any point, Philip is in the same cell with a train, he loses. If the train reaches the left column, it continues to move as before, leaving the tunnel.

Your task is to answer the question whether there is a sequence of movements of Philip, such that he would be able to get to the rightmost column.

 [Image] 


-----Input-----

Each test contains from one to ten sets of the input data. The first line of the test contains a single integer t (1 ≤ t ≤ 10 for pretests and tests or t = 1 for hacks; see the Notes section for details) — the number of sets.

Then follows the description of t sets of the input data. 

The first line of the description of each set contains two integers n, k (2 ≤ n ≤ 100, 1 ≤ k ≤ 26) — the number of columns on the field and the number of trains. Each of the following three lines contains the sequence of n character, representing the row of the field where the game is on. Philip's initial position is marked as 's', he is in the leftmost column. Each of the k trains is marked by some sequence of identical uppercase letters of the English alphabet, located in one line. Distinct trains are represented by distinct letters. Character '.' represents an empty cell, that is, the cell that doesn't contain either Philip or the trains.


-----Output-----

For each set of the input data print on a single line word YES, if it is possible to win the game and word NO otherwise.


-----Examples-----
Input
2
16 4
...AAAAA........
s.BBB......CCCCC
........DDDDD...
16 4
...AAAAA........
s.BBB....CCCCC..
.......DDDDD....

Output
YES
NO

Input
2
10 4
s.ZZ......
.....AAABB
.YYYYYY...
10 4
s.ZZ......
....AAAABB
.YYYYYY...

Output
YES
NO



-----Note-----

In the first set of the input of the first sample Philip must first go forward and go down to the third row of the field, then go only forward, then go forward and climb to the second row, go forward again and go up to the first row. After that way no train blocks Philip's path, so he can go straight to the end of the tunnel.

Note that in this problem the challenges are restricted to tests that contain only one testset.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Shortest paths

Starter code:

Solutions:
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
import bisect
mod = 998244353
from collections import Counter
import bisect
from heapq import *
from collections import defaultdict, deque

def okay(x, y):
	if x < 0 or x >= 3:
		return False
	if y < n and mat[x][y] != '.':
		return False
	if y + 1 < n and mat[x][y + 1] != '.':
		return False
	if y + 2 < n and mat[x][y + 2] != '.':
		return False
	return True
from collections import deque
t = int(input())
for _ in range(t):
	q = deque([])
	flag = False
	(n, k) = map(int, input().split())
	mat = [input() for i in range(3)]
	vis = [[0 for i in range(105)] for j in range(3)]
	for i in range(3):
		if mat[i][0] == 's':
			q.append((i, 0))
	while q:
		(x, y) = q.popleft()
		if y + 1 >= n:
			flag = True
			break
		if vis[x][y] == 1:
			continue
		vis[x][y] = 1
		if y + 1 < n and mat[x][y + 1] == '.' and (okay(x - 1, y + 1) == True):
			q.append((x - 1, y + 3))
		if y + 1 < n and mat[x][y + 1] == '.' and (okay(x, y + 1) == True):
			q.append((x, y + 3))
		if y + 1 < n and mat[x][y + 1] == '.' and (okay(x + 1, y + 1) == True):
			q.append((x + 1, y + 3))
	if flag:
		print('YES')
	else:
		print('NO')


t = int(input())
cmi = [0, -1, 1]

def dfs(i, j, data, n):
	stacki = list()
	stackj = list()
	stacki.append(i)
	stackj.append(j)
	while len(stacki) != 0:
		ti = stacki.pop()
		tj = stackj.pop()
		for i in range(0, 3):
			nexti = ti + cmi[i]
			nextj = tj + 3
			if not (0 <= nexti and nexti <= 2):
				continue
			isb = True
			for nn in [(ti, tj + 1), (nexti, tj + 1), (nexti, tj + 2), (nexti, tj + 3)]:
				(tti, ttj) = nn
				if ttj < n and data[tti][ttj] == False:
					isb = False
					break
			if isb == False:
				continue
			if nextj >= n:
				return True
			else:
				data[nexti][nextj] = False
				stacki.append(nexti)
				stackj.append(nextj)
	return False
for i in range(0, t):
	(n, k) = map(int, input().split())
	si = 0
	sj = 0
	data = list()
	for j in range(0, 3):
		s = input()
		tmp = list()
		for k in range(0, n):
			if s[k] == 's':
				si = j
				sj = k
				tmp.append(True)
			elif s[k] != '.':
				tmp.append(False)
			else:
				tmp.append(True)
		data.append(tmp)
	print(['NO', 'YES'][dfs(si, sj, data, n)])


from queue import Queue
from collections import defaultdict

class PhilipTrains:

	def __init__(self, n, k, state):
		self.n = n
		self.k = k
		self.state = state
		self.graph = [[[0 for i in range(n + 1)] for j in range(n)] for k in range(3)]
		for i in range(len(state)):
			for j in range(len(state[i])):
				if 'A' <= state[i][j] <= 'Z':
					for k in range(n):
						nj = j - 2 * k
						if nj >= 0:
							self.graph[i][nj][k] = -1
						else:
							break
		for i in range(len(state)):
			if state[i][0] == 's':
				self.r = i
				self.c = 0

	def check_reach(self):
		q = Queue()
		check = defaultdict(int)
		changes = [(1, 1, 1), (-1, 1, 1), (0, 1, 1)]
		q.put((self.r, self.c, 0))
		check[self.r, self.c, 0] = 1
		while not q.empty():
			(pr, pc, pt) = q.get()
			if self.graph[pr][pc][pt] == -1:
				continue
			if pc == self.n - 1:
				return 'YES'
			if self.graph[pr][pc + 1][pt] != -1:
				if check[pr, pc + 1, pt + 1] != 1:
					q.put((pr, pc + 1, pt + 1))
					check[pr, pc + 1, pt + 1] = 1
				for ch in [1, -1]:
					if 0 <= pr + ch <= 2 and check[pr + ch, pc + 1, pt + 1] != 1 and (self.graph[pr + ch][pc + 1][pt] != -1):
						q.put((pr + ch, pc + 1, pt + 1))
						check[pr + ch, pc + 1, pt + 1] = 1
		return 'NO'
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().strip(' ').split(' ')))
	arr = []
	for i in range(3):
		arr.append(input().strip(' '))
	graph = PhilipTrains(n, k, arr)
	print(graph.check_reach())


def safe(mat, x, y, n):
	if not x in [0, 1, 2]:
		return False
	for i in range(1, 4):
		if y + i < n and mat[x][y + i] != '.':
			return False
	return True

def dfs(mat, n):
	pos = 0
	for k in range(3):
		if mat[k][0] == 's':
			pos = k
	vis = {}
	s = [(pos, 0)]
	while s:
		(x, y) = s.pop()
		if y >= n:
			return 'YES'
		if (x, y) in vis:
			continue
		vis[x, y] = 1
		for i in [-1, 0, 1]:
			if y + 1 >= n or (y + 1 < n and mat[x][y + 1] == '.' and safe(mat, x + i, y, n)):
				s.append((x + i, y + 3))
	return 'NO'
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	mat = [input() for i in range(3)]
	print(dfs(mat, n))


def dfs(x, y):
	global f
	pos.append((x, y))
	y += 1
	if f or str(gr[x][y]).isalpha():
		return
	if y >= q - 1:
		f = True
		return
	if not str(gr[x][y + 1]).isalpha():
		if not str(gr[x][y + 2]).isalpha():
			if (x, y + 2) not in pos:
				dfs(x, y + 2)
	if x > 0:
		if not str(gr[x - 1][y]).isalpha():
			if not str(gr[x - 1][y + 1]).isalpha():
				if not str(gr[x - 1][y + 2]).isalpha():
					if (x - 1, y + 2) not in pos:
						dfs(x - 1, y + 2)
	if x < 2:
		if not str(gr[x + 1][y]).isalpha():
			if not str(gr[x + 1][y + 1]).isalpha():
				if not str(gr[x + 1][y + 2]).isalpha():
					if (x + 1, y + 2) not in pos:
						dfs(x + 1, y + 2)
n = int(input())
for i in range(n):
	(q, w) = [int(i) for i in input().split()]
	gr = list()
	gr.append(input() + '     ')
	gr.append(input() + '     ')
	gr.append(input() + '     ')
	pos = []
	f = False
	for i in range(3):
		if gr[i][0] == 's':
			gr[i] = ' ' + gr[i][1:]
			dfs(i, 0)
			break
	if f:
		print('YES')
	else:
		print('NO')


def R(i, j):
	if i < n:
		smas[j][i] = 1
		p = False
		if mas[j][i + 1] == '.':
			if mas[j][i + 3] == '.' and smas[j][i + 3] == 0:
				p = p or R(i + 3, j)
			if j > 0 and mas[j - 1][i + 1] == '.' and (mas[j - 1][i + 3] == '.') and (smas[j - 1][i + 3] == 0):
				p = p or R(i + 3, j - 1)
			if j < 2 and mas[j + 1][i + 1] == '.' and (mas[j + 1][i + 3] == '.') and (smas[j + 1][i + 3] == 0):
				p = p or R(i + 3, j + 1)
		return p
	else:
		return True
t = int(input())
for l in range(t):
	(n, k) = map(int, input().split(' '))
	s = 0
	s1 = input() + '.....'
	if s1[0] == 's':
		s = 0
	s2 = input() + '.....'
	if s2[0] == 's':
		s = 1
	s3 = input() + '.....'
	if s3[0] == 's':
		s = 2
	mas = []
	mas.append(list(s1))
	mas.append(list(s2))
	mas.append(list(s3))
	smas = []
	smas.append([0] * (n + 5))
	smas.append([0] * (n + 5))
	smas.append([0] * (n + 5))
	print('YES') if R(0, s) else print('NO')


T = int(input())
for t in range(T):
	(n, k) = map(int, input().split(' ')[:2])
	s = ['', '', '']
	for i in range(3):
		s[i] = input()
	s[0] += '.' * (n * 3)
	s[1] += '.' * (n * 3)
	s[2] += '.' * (n * 3)

	def top():
		return [s[0][0] != '.', s[1][0] != '.', s[2][0] != '.']

	def shift():
		s[0] = s[0][1:]
		s[1] = s[1][1:]
		s[2] = s[2][1:]
		return top()
	p = [s[0][0] == 's', s[1][0] == 's', s[2][0] == 's']
	for i in range(1, n):
		np = [False, False, False]
		if p[0] == True and s[0][1] == '.':
			np[0] = True
			np[1] = True
		if p[1] == True and s[1][1] == '.':
			np[0] = True
			np[1] = True
			np[2] = True
		if p[2] == True and s[2][1] == '.':
			np[1] = True
			np[2] = True
		p = np
		(s0, s1, s2) = shift()
		if s0:
			p[0] = False
		if s1:
			p[1] = False
		if s2:
			p[2] = False
		(s0, s1, s2) = shift()
		if s0:
			p[0] = False
		if s1:
			p[1] = False
		if s2:
			p[2] = False
		(s0, s1, s2) = shift()
		if s0:
			p[0] = False
		if s1:
			p[1] = False
		if s2:
			p[2] = False
	if p[0] or p[1] or p[2]:
		print('YES')
	else:
		print('NO')


import sys
from collections import deque
read = lambda : list(map(int, sys.stdin.readline().split()))
(t,) = read()
for _ in range(t):
	(n, k) = read()
	r = [list(sys.stdin.readline().strip() + '...') for _ in range(3)]
	for x in range(n):
		for y in range(3):
			if r[y][x] == 's' and r[y][x + 1] in '.s':
				for y2 in range(3):
					if abs(y - y2) <= 1 and r[y2][x + 1] in '.s':
						if r[y2][x + 2] in '.s' and r[y2][x + 3] in '.s':
							r[y2][x + 3] = 's'
	if any((r[y][x] == 's' for y in range(3) for x in range(n - 1, n + 3))):
		print('YES')
	else:
		print('NO')


def dfs(x, y):
	vis.append((x, y))
	y += 1
	global flag
	if flag or str.isalpha(grid[x][y]):
		return
	if y >= n - 1:
		flag = True
		return
	if not str.isalpha(grid[x][y + 1]) and (not str.isalpha(grid[x][y + 2])) and ((x, y + 2) not in vis):
		dfs(x, y + 2)
	if x > 0 and (not str.isalpha(grid[x - 1][y])) and (not str.isalpha(grid[x - 1][y + 1])) and (not str.isalpha(grid[x - 1][y + 2])) and ((x - 1, y + 2) not in vis):
		dfs(x - 1, y + 2)
	if x < 2 and (not str.isalpha(grid[x + 1][y])) and (not str.isalpha(grid[x + 1][y + 1])) and (not str.isalpha(grid[x + 1][y + 2])) and ((x + 1, y + 2) not in vis):
		dfs(x + 1, y + 2)
T = int(input())
for loop in range(T):
	(n, k) = [int(i) for i in input().split()]
	grid = list()
	grid.append(input() + '    ')
	grid.append(input() + '    ')
	grid.append(input() + '    ')
	vis = list()
	flag = False
	for i in range(3):
		if grid[i][0] == 's':
			grid[i] = ' ' + grid[i][1:]
			dfs(i, 0)
			break
	if flag:
		print('YES')
	else:
		print('NO')


def solve(n, k, arr, pos):
	i = 0
	positions = [pos]
	while i < n - 3:
		previousPositions = positions[:]
		positions = []
		i += 1
		for m in range(3):
			if arr[m][i] == '.' and arr[m][i + 2] == '.':
				for q in previousPositions:
					if abs(m - q) <= 1 and arr[q][i] == '.':
						if m not in positions:
							positions.append(m)
		i += 2
	for q in positions:
		for u in range(i, n):
			if arr[q][u] != '.':
				positions.remove(q)
				break
	if positions != []:
		print('YES')
	else:
		print('NO')
t = int(input())
for x in range(t):
	arr = []
	(n, k) = map(int, input().split())
	for i in range(3):
		line = list(input())
		arr.append(line)
		if 's' in line:
			pos = i
	solve(n, k, arr, pos)


import sys
flag = False
t = int(input())
for kek in range(t):
	(n, k) = [int(i) for i in input().split()]
	if t == 10 and n == 95 and (k == 6):
		flag = True
	a = [[0] * n for i in range(3)]
	for i in range(3):
		a[i] = [i for i in input()]
	dp = [[False] * n for i in range(3)]
	l = 0
	if a[0][0] == 's':
		l = 0
	if a[1][0] == 's':
		l = 1
	if a[2][0] == 's':
		l = 2
	dp[l][0] = True
	first = [[False] * n for i in range(3)]
	bad = [True] * 3
	for i in range(1, n):
		if 3 * i < n and a[0][3 * i] == '.' and (a[0][3 * i - 2] == '.'):
			if (dp[0][i - 1] or first[0][i - 1]) or (a[1][3 * i - 2] == '.' and dp[1][i - 1]):
				dp[0][i] = True
		elif 3 * i >= n > 3 * i - 2:
			if dp[0][i - 1] and a[0][3 * i - 2] == '.' or (dp[1][i - 1] and a[1][3 * i - 2] == '.'):
				dp[0][i] = True
		elif 3 * i >= n and (dp[0][i - 1] or dp[1][i - 1]):
			dp[0][i] = True
		if 3 * i < n and a[1][3 * i] == '.' and (a[1][3 * i - 2] == '.'):
			if (dp[1][i - 1] or first[1][i - 1]) or (a[0][3 * i - 2] == '.' and dp[0][i - 1]) or (a[2][3 * i - 2] == '.' and dp[2][i - 1]):
				dp[1][i] = True
		elif 3 * i >= n > 3 * i - 2:
			if dp[0][i - 1] and a[0][3 * i - 2] == '.' or (dp[1][i - 1] and a[1][3 * i - 2] == '.') or (dp[2][i - 1] and a[2][3 * i - 2] == '.'):
				dp[1][i] = True
		elif 3 * i >= n and (dp[0][i - 1] or dp[1][i - 1] or dp[2][i - 1]):
			dp[1][i] = True
		if 3 * i < n and a[2][3 * i] == '.' and (a[2][3 * i - 2] == '.'):
			if (dp[2][i - 1] or first[2][i - 1]) or (a[1][3 * i - 2] == '.' and dp[1][i - 1]):
				dp[2][i] = True
		elif 3 * i >= n > 3 * i - 2:
			if dp[2][i - 1] and a[2][3 * i - 2] == '.' or (dp[1][i - 1] and a[1][3 * i - 2] == '.'):
				dp[2][i] = True
		elif 3 * i >= n and (dp[1][i - 1] or dp[2][i - 1]):
			dp[2][i] = True
	if max(dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]):
		print('YES')
	else:
		print('NO')


def shift(a, n):
	b = [['.' for i in range(n)] for i in range(3)]
	for i in range(3):
		for j in range(n - 2):
			b[i][j] = a[i][j + 2]
	return b
n = int(input())
for case in range(n):
	(n, k) = [int(i) for i in input().split()]
	a = []
	for i in range(3):
		a.append(list(input()))
	m = [[False for i in range(n)] for j in range(3)]
	for i in range(3):
		if a[i][0] == 's':
			m[i][0] = True
	for i in range(1, n):
		for j in range(3):
			if m[j][i - 1] and a[j][i] == '.' and (a[j][i - 1] == '.' or a[j][i - 1] == 's') and (i < 2 or a[j][i - 2] == '.'):
				m[j][i] = True
		ms = [False for something in range(3)]
		if m[0][i]:
			if a[1][i] == '.':
				ms[1] = True
		if m[1][i]:
			if a[0][i] == '.':
				ms[0] = True
			if a[2][i] == '.':
				ms[2] = True
		if m[2][i]:
			if a[1][i] == '.':
				ms[1] = True
		for j in range(3):
			if ms[j]:
				m[j][i] = True
		a = shift(a, n)
	for i in range(3):
		if m[i][n - 1]:
			print('YES')
			break
	else:
		print('NO')


def handle_test():
	(n, k) = [int(v) for v in input().split()]
	field = [input() for _ in range(3)]
	if field[0][0] == 's':
		cpos = [0, 0]
	elif field[1][0] == 's':
		cpos = [1, 0]
	else:
		cpos = [2, 0]
	available = [[False] * len(field[0]) for _ in range(3)]
	available[cpos[0]][cpos[1]] = True
	for i in range(n):
		for j in range(3):
			if available[j][i]:
				if i + 1 >= n:
					return True
				elif field[j][i + 1] != '.':
					continue
				for offset in (-1, 0, 1):
					if not 0 <= j + offset < 3 or field[j + offset][i + 1] != '.':
						continue
					if i + 2 >= n:
						return True
					elif field[j + offset][i + 2] != '.':
						continue
					elif i + 3 >= n:
						return True
					elif field[j + offset][i + 3] != '.':
						continue
					else:
						available[j + offset][i + 3] = True
	return False
t = int(input())
for _ in range(t):
	print(['NO', 'YES'][handle_test()])


t = int(input())
for o in range(t):
	(l, cnt) = map(int, input().split())
	a = [list(input()) for j in range(3)]
	for i in range(l - 1):
		for j in range(3):
			if a[j][i] == 's' and (a[j][i + 1] == '.' or a[j][i + 1] == 's'):
				if a[j][i + 1] == '.':
					a[j][i + 1] = 's'
				if j > 0 and a[j - 1][i + 1] == '.':
					a[j - 1][i + 1] = 's'
				if j < 2 and a[j + 1][i + 1] == '.':
					a[j + 1][i + 1] = 's'
		for u in range(2):
			for q in range(3):
				for w in range(l):
					if a[q][w] >= 'A' and a[q][w] <= 'Z' and (w == l - 1 or a[q][w + 1] != a[q][w]):
						a[q][w] = '.'
					if w < l - 1 and a[q][w + 1] >= 'A' and (a[q][w + 1] <= 'Z') and (a[q][w + 1] != a[q][w]):
						a[q][w] = a[q][w + 1]
	if a[0][l - 1] == 's' or a[1][l - 1] == 's' or a[2][l - 1] == 's':
		print('YES')
	else:
		print('NO')


t = int(input())
for kek in range(t):
	(n, k) = [int(i) for i in input().split()]
	a = [[0] * n for i in range(3)]
	for i in range(3):
		a[i] = [i for i in input()]
	dp = [[False] * n for i in range(3)]
	l = 0
	if a[0][0] == 's':
		l = 0
	if a[1][0] == 's':
		l = 1
	if a[2][0] == 's':
		l = 2
	dp[l][0] = True
	first = [[False] * n for i in range(3)]
	for i in range(1, n):
		if 3 * i < n and a[0][3 * i] == '.' and (a[0][3 * i - 2] == '.'):
			if (dp[0][i - 1] or first[0][i - 1]) or (a[1][3 * i - 2] == '.' and dp[1][i - 1]):
				dp[0][i] = True
		elif 3 * i >= n > 3 * i - 2:
			if dp[0][i - 1] and a[0][3 * i - 2] == '.' or (dp[1][i - 1] and a[1][3 * i - 2] == '.'):
				dp[0][i] = True
		elif 3 * i >= n and (dp[0][i - 1] or dp[1][i - 1]):
			dp[0][i] = True
		if 3 * i < n and a[1][3 * i] == '.' and (a[1][3 * i - 2] == '.'):
			if (dp[1][i - 1] or first[1][i - 1]) or (a[0][3 * i - 2] == '.' and dp[0][i - 1]) or (a[2][3 * i - 2] == '.' and dp[2][i - 1]):
				dp[1][i] = True
		elif 3 * i >= n > 3 * i - 2:
			if dp[0][i - 1] and a[0][3 * i - 2] == '.' or (dp[1][i - 1] and a[1][3 * i - 2] == '.') or (dp[2][i - 1] and a[2][3 * i - 2] == '.'):
				dp[1][i] = True
		elif 3 * i >= n and (dp[0][i - 1] or dp[1][i - 1] or dp[2][i - 1]):
			dp[1][i] = True
		if 3 * i < n and a[2][3 * i] == '.' and (a[2][3 * i - 2] == '.'):
			if (dp[2][i - 1] or first[2][i - 1]) or (a[1][3 * i - 2] == '.' and dp[1][i - 1]):
				dp[2][i] = True
		elif 3 * i >= n > 3 * i - 2:
			if dp[2][i - 1] and a[2][3 * i - 2] == '.' or (dp[1][i - 1] and a[1][3 * i - 2] == '.'):
				dp[2][i] = True
		elif 3 * i >= n and (dp[1][i - 1] or dp[2][i - 1]):
			dp[2][i] = True
	if max(dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]):
		print('YES')
	else:
		print('NO')


from collections import deque
grid = [None, None, None]

def solve():
	(n, k) = map(int, input().split())
	for i in range(3):
		grid[i] = input() + '...'
	q = deque([(0 if grid[0][0] == 's' else 1 if grid[1][0] == 's' else 2, 0)])
	used = [[False] * (n + 3) for i in range(3)]
	while q:
		(y, x) = q.popleft()
		if x >= n:
			return 'YES'
		if used[y][x]:
			continue
		used[y][x] = True
		a = grid[y][x + 1]
		if a == grid[y][x + 2] == grid[y][x + 3] == '.':
			q.append((y, x + 3))
		if y > 0 and a == grid[y - 1][x + 1] == grid[y - 1][x + 2] == grid[y - 1][x + 3] == '.':
			q.append((y - 1, x + 3))
		if y < 2 and a == grid[y + 1][x + 1] == grid[y + 1][x + 2] == grid[y + 1][x + 3] == '.':
			q.append((y + 1, x + 3))
	return 'NO'
t = int(input())
for test in range(t):
	print(solve())


def bfs(mat, x, y, n):
	queue = [[x, y, 0]]
	mark = {j: {u: False for u in range(n)} for j in range(3)}
	n -= 1
	while queue:
		q = queue.pop(0)
		(a, b, c) = (q[0], q[1], q[2])
		if mark[a][b] == True:
			continue
		mark[a][b] = True
		if b == n:
			return 'YES'
		c += 2
		(e, r, f) = (0, 0, 0)
		p = min(b - 1 + c, n)
		z = min(b + 2 + c, n)
		for i in range(p, z):
			if mat[0][i] != '.':
				e = 1
			if mat[1][i] != '.':
				r = 1
			if mat[2][i] != '.':
				f = 1
		if mat[a][p] == '.' or p == n:
			if e == 0:
				if a == 1 or a == 0:
					if mark[0][b + 1] == False:
						queue.append([0, b + 1, c])
			if r == 0:
				if mark[1][b + 1] == False:
					queue.append([1, b + 1, c])
			if f == 0:
				if a == 1 or a == 2:
					if mark[2][b + 1] == False:
						queue.append([2, b + 1, c])
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	mat = {j: {u: x for (u, x) in enumerate(input())} for j in range(3)}
	if mat[0][0] == 's':
		res = bfs(mat, 0, 0, n)
	elif mat[1][0] == 's':
		res = bfs(mat, 1, 0, n)
	else:
		res = bfs(mat, 2, 0, n)
	if res == None:
		print('NO')
	else:
		print('YES')


def simulate(grid):
	(n, m) = (len(grid), len(grid[0]))
	threshold = n * [m]
	for r in range(n):
		c = m - 1
		while c >= 0 and grid[r][c] == '.':
			c -= 1
		threshold[r] = c + 1
	in_row = n * [False]
	for r in range(n):
		if grid[r][0] == 's':
			in_row[r] = True
			break
	c = 0
	while True:
		next_in_row = n * [False]
		for (r, possible) in enumerate(in_row):
			if not possible:
				continue
			if c + 1 >= threshold[r]:
				return True
			if grid[r][c + 1] != '.':
				continue
			for rr in range(max(0, r - 1), min(r + 2, n)):
				okay = True
				for cc in range(c + 1, c + 4):
					if cc >= threshold[rr]:
						return True
					if grid[rr][cc] != '.':
						okay = False
						break
				if okay:
					next_in_row[rr] = True
		in_row = next_in_row
		c += 3
		if True not in in_row:
			return False
num_cases = int(input())
for case_index in range(num_cases):
	(m, k) = map(int, input().split())
	grid = [list(input().strip()) for r in range(3)]
	if simulate(grid):
		print('YES')
	else:
		print('NO')


def check(graph, xx, yy):
	n = len(graph[0])
	if yy >= n:
		return True
	elif xx >= 0 and xx < 3 and (graph[xx][yy] == '.'):
		return True
	else:
		return False

def DFS(graph):
	man_x = 0
	man_y = 0
	for i in range(3):
		if graph[i][0] == 's':
			man_x = i
			break
	qun1 = []
	qun1.append([man_x, man_y])
	qun2 = set()
	qun2.add((man_x, man_y))
	ans = False
	while qun1:
		temp = qun1.pop(0)
		temp_x = temp[0]
		temp_y = temp[1]
		if check(graph, temp_x, temp_y + 1) and check(graph, temp_x, temp_y + 2) and check(graph, temp_x, temp_y + 3):
			if temp_y + 3 >= n:
				ans = True
				break
			if (temp_x, temp_y + 3) not in qun2:
				qun1.append([temp_x, temp_y + 3])
				qun2.add((temp_x, temp_y + 3))
		if check(graph, temp_x, temp_y + 1) and check(graph, temp_x + 1, temp_y + 1) and check(graph, temp_x + 1, temp_y + 2) and check(graph, temp_x + 1, temp_y + 3):
			if temp_y + 3 >= n:
				ans = True
				break
			if (temp_x + 1, temp_y + 3) not in qun2:
				qun1.append([temp_x + 1, temp_y + 3])
				qun2.add((temp_x + 1, temp_y + 3))
		if check(graph, temp_x, temp_y + 1) and check(graph, temp_x - 1, temp_y + 1) and check(graph, temp_x - 1, temp_y + 2) and check(graph, temp_x - 1, temp_y + 3):
			if temp_y + 3 >= n:
				ans = True
				break
			if (temp_x - 1, temp_y + 3) not in qun2:
				qun1.append([temp_x - 1, temp_y + 3])
				qun2.add((temp_x - 1, temp_y + 3))
	return ans
t = int(input())
while t > 0:
	t -= 1
	str1 = input().split()
	n = int(str1[0])
	k = int(str1[1])
	graph = []
	s1 = input()
	graph.append(s1)
	s2 = input()
	graph.append(s2)
	s3 = input()
	graph.append(s3)
	if DFS(graph) is True:
		print('YES')
	else:
		print('NO')


def read_numbers():
	return list(map(int, input().split()))

def f(dim, track):
	possible = [i[0] == 's' for i in track]
	for i in range(1, dim[0], 3):
		new_possible = [False, False, False]
		if possible[0] and track[0][i] == '.' or (possible[1] and track[1][i] == '.' == track[0][i]):
			new_possible[0] = True
		if possible[0] and track[0][i] == '.' == track[1][i] or (possible[1] and track[1][i] == '.') or (possible[2] and track[2][i] == '.' == track[1][i]):
			new_possible[1] = True
		if possible[1] and track[1][i] == '.' == track[2][i] or (possible[2] and track[2][i] == '.'):
			new_possible[2] = True
		possible = new_possible
		for j in range(i + 1, min(i + 3, dim[0])):
			possible = [possible[k] and track[k][j] == '.' for k in range(3)]
	return 'YES' if any(possible) else 'NO'
n = int(input())
for _ in range(n):
	dim = read_numbers()
	track = [input() for _ in range(3)]
	print(f(dim, track))


t = int(input())
for test in range(t):
	(n, k) = [int(i) for i in input().split()]
	grid = [[True for i in range(3)] for i in range(n)]
	ok = [[False for i in range(3)] for i in range(n)]
	rx = 0
	ry = 0
	for i in range(3):
		row = input()
		j = 0
		for v in row:
			if v == 's':
				rx = j
				ry = i
			elif v != '.':
				grid[j][i] = False
			j += 1

	def verify(x, y):
		if x < n and y < 3 and (x >= 0) and (y >= 0):
			return grid[x][y]
		else:
			return False

	def dfs(x, y):
		global ok
		if not ok[x][y]:
			ok[x][y] = True
			if verify(x + 1, y) and verify(x + 3, y):
				dfs(x + 3, y)
			if verify(x + 1, y) and verify(x + 1, y + 1) and verify(x + 3, y + 1):
				dfs(x + 3, y + 1)
			if verify(x + 1, y) and verify(x + 1, y - 1) and verify(x + 3, y - 1):
				dfs(x + 3, y - 1)
			if x + 2 >= n - 1:
				if verify(x + 1, y):
					dfs(x + 1, y)
	dfs(rx, ry)
	res = False
	for i in range(3):
		if ok[n - 1][i]:
			res = True
	if res:
		print('YES')
	else:
		print('NO')


def checkPoint(graph, x, y):
	n = len(graph)
	m = len(graph[0])
	if y >= m:
		return True
	if x >= 0 and x < n and (y >= 0) and (graph[x][y] == '.'):
		return True
	return False

def BFS(graph):
	queue = []
	vis = set()
	x = 0
	y = 0
	ans = False
	m = len(graph[0])
	for i in range(3):
		if graph[i][y] == 's':
			x = i
			break
	queue.append((x, y))
	vis.add((x, y))
	while len(queue) > 0:
		currentPosition = queue.pop(0)
		currentx = currentPosition[0]
		currenty = currentPosition[1]
		if checkPoint(graph, currentx, currenty + 1) and checkPoint(graph, currentx, currenty + 2) and checkPoint(graph, currentx, currenty + 3):
			if currenty + 3 >= m - 1:
				ans = True
				break
			if (currentx, currenty + 3) not in vis:
				queue.append((currentx, currenty + 3))
				vis.add((currentx, currenty + 3))
		if checkPoint(graph, currentx, currenty + 1) and checkPoint(graph, currentx - 1, currenty + 1) and checkPoint(graph, currentx - 1, currenty + 2) and checkPoint(graph, currentx - 1, currenty + 3):
			if currenty + 3 >= m - 1:
				ans = True
				break
			if (currentx - 1, currenty + 3) not in vis:
				queue.append((currentx - 1, currenty + 3))
				vis.add((currentx - 1, currenty + 3))
		if checkPoint(graph, currentx, currenty + 1) and checkPoint(graph, currentx + 1, currenty + 1) and checkPoint(graph, currentx + 1, currenty + 2) and checkPoint(graph, currentx + 1, currenty + 3):
			currentx += 1
			currenty += 3
			if currenty >= m - 1:
				ans = True
				break
			if (currentx, currenty) not in vis:
				queue.append((currentx, currenty))
				vis.add((currentx, currenty))
	return ans
t = int(input())
while t > 0:
	t -= 1
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	graph = []
	k = 3
	while k > 0:
		k -= 1
		s = input()
		graph.append(s)
	ans = BFS(graph)
	if ans == True:
		print('YES')
	else:
		print('NO')


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def main():
	(n, k) = mints()
	a = [list(minp()) for i in range(3)]
	w = [[False] * (n + 1) for i in range(3)]
	for j in range(3):
		if a[j][0] == 's':
			a[j][0] = '.'
			w[j][0] = True
	for i in range(n):
		for j in range(3):
			if w[j][i]:
				if i * 3 + 1 >= n or a[j][i * 3 + 1] == '.':
					for z in range(max(j - 1, 0), min(j + 2, 3)):
						if (i * 3 + 1 >= n or a[z][i * 3 + 1] == '.') and (i * 3 + 2 >= n or a[z][i * 3 + 2] == '.') and (i * 3 + 3 >= n or a[z][i * 3 + 3] == '.'):
							w[z][i + 1] = True
	can = w[0][n] or w[1][n] or w[2][n]
	if can:
		print('YES')
	else:
		print('NO')
t = mint()
for i in range(t):
	main()


import sys
t = int(next(sys.stdin))

def dfs(grid, pos, n):
	stack = []
	visited = [[False for _ in range(n)] for _ in range(3)]
	stack.append(pos)
	while len(stack):
		(x, y) = stack.pop()
		if y >= n:
			return 'YES'
		if visited[x][y]:
			continue
		visited[x][y] = True
		for move in [-1, 0, 1]:
			if y + 1 >= n or (grid[x][y + 1] == '.' and x + move in [0, 1, 2] and all((y + i >= n or grid[x + move][y + i] == '.' for i in range(1, 4)))):
				stack.append((x + move, y + 3))
	return 'NO'
for _ in range(t):
	(n, k) = map(int, next(sys.stdin).split())
	grid = []
	pos = (-1, -1)
	for i in range(3):
		grid.append(next(sys.stdin))
		if grid[i][0] == 's':
			pos = (i, 0)
	print(dfs(grid, pos, n))