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: competition

Starter code:

Solutions:
def dfs(x, y):
    vis.append((x, y))
    y += 1
    nonlocal flag
    if flag or str.isalpha(grid[x][y]):
        return
    if y >= n - 1:
        flag = True
        return
    
    # stay idle
    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)

    # move down
    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)

    #move up
    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")

T = int(input())

for t in range(T):
    n, k = list(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

        # my move ended

        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")


def dfs(x,y):
    nonlocal 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")

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
    #for i in range(3):
    #    print(dp[i])
    if max(dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]):
        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
    #for i in range(3):
    #    print(dp[i])
    if max(dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]):
        print('YES')
    else:
        print('NO')


# import sys

# sys.stdin = open('cf586d.in')



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()])



# Made By Mostafa_Khaled


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')

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]
	#print(w)
	if can:
		print("YES")
	else:
		print("NO")

t = mint()
for i in range(t):
	main()

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))

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)]
	#x-col, y-row

	rx = 0; ry = 0
	for i in range(3):
		row = input()
		j=0
		for v in row:
			if v=='s':
				#print("here")
				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):
		nonlocal ok
		if not ok[x][y]:
			#print(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)


			#end game(tap in)
			if x+2>=n-1:
				if verify(x+1,y):
					dfs(x+1,y)

	dfs(rx, ry)
	#print(rx, ry)
	#print(ok)

	res = False
	for i in range(3):
		if ok[n-1][i]:
			res=True

	if res:
		print("YES")
	else:
		print("NO")