Vivek has encountered a problem. He has a maze that can be represented as an $n \times m$ grid. Each of the grid cells may represent the following:  Empty — '.'  Wall — '#'  Good person  — 'G'  Bad person — 'B' 

The only escape from the maze is at cell $(n, m)$.

A person can move to a cell only if it shares a side with their current cell and does not contain a wall. Vivek wants to block some of the empty cells by replacing them with walls in such a way, that all the good people are able to escape, while none of the bad people are able to. A cell that initially contains 'G' or 'B' cannot be blocked and can be travelled through.

Help him determine if there exists a way to replace some (zero or more) empty cells with walls to satisfy the above conditions.

It is guaranteed that the cell $(n,m)$ is empty. Vivek can also block this cell.


-----Input-----

The first line contains one integer $t$ $(1 \le t \le 100)$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$, $m$ $(1 \le n, m \le 50)$ — the number of rows and columns in the maze.

Each of the next $n$ lines contain $m$ characters. They describe the layout of the maze. If a character on a line equals '.', the corresponding cell is empty. If it equals '#', the cell has a wall. 'G' corresponds to a good person and 'B' corresponds to a bad person.


-----Output-----

For each test case, print "Yes" if there exists a way to replace some empty cells with walls to satisfy the given conditions. Otherwise print "No"

You may print every letter in any case (upper or lower).


-----Example-----
Input
6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#..
GG.
2 2
#B
B.

Output
Yes
Yes
No
No
Yes
Yes



-----Note-----

For the first and second test cases, all conditions are already satisfied.

For the third test case, there is only one empty cell $(2,2)$, and if it is replaced with a wall then the good person at $(1,2)$ will not be able to escape.

For the fourth test case, the good person at $(1,1)$ cannot escape.

For the fifth test case, Vivek can block the cells $(2,3)$ and $(2,2)$.

For the last test case, Vivek can block the destination cell $(2, 2)$.

Difficulty: interview

Starter code:

Solutions:
t = int(input())

for _ in range(t):
    n, m = [int(x) for x in input().split()]
    grid = [list(input()) for _ in range(n)]

    has_good = any('G' in l for l in grid)

    if not has_good:
        print("Yes")
        continue

    impossible = False
    for i in range(n):
        for j in range(m):
            if grid[i][j] != 'B':
                continue

            for nbi, nbj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= nbi < n and 0 <= nbj < m:
                    if grid[nbi][nbj] == 'G':
                        impossible = True
                        break
                    elif grid[nbi][nbj] == 'B' or grid[nbi][nbj] == '#':
                        continue
                    elif grid[nbi][nbj] == '.':
                        grid[nbi][nbj] = "#"
                    else:
                        assert False, "What's in the grid?"

    if grid[n-1][m-1] == '#' or impossible:
        print("No")
        continue

    seen = [[False]*m for _ in range(n)]
    stack = [(n-1, m-1)]
    seen[n-1][m-1] = True

    while len(stack):
        i, j = stack.pop()

        for nbi, nbj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if 0 <= nbi < n and 0 <= nbj < m:
                if grid[nbi][nbj] != '#' and not seen[nbi][nbj]:
                    seen[nbi][nbj] = True
                    stack.append((nbi, nbj))

    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'G' and not seen[i][j]:
                impossible = True
                break
        if impossible:
            break

    if impossible:
        print("No")
    else:
        print("Yes")


from collections import deque

T = int(input())


class Found(Exception):
    pass


def neighbours(M, i, j):
    res = []
    if i > 0:
        res.append((i-1, j))
    if j > 0:
        res.append((i, j-1))
    if i+1 < len(M):
        res.append((i+1, j))
    if j+1 < len(M[0]):
        res.append((i, j+1))
    return res


def bfs(M, i, j):
    visited = [[False]*len(M[0]) for _ in range(len(M))]
    visited[i][j] = True
    Q = deque()
    Q.append((i, j))
    answer = 0
    if M[i][j] == 'G':
        answer += 1

    while Q:
        eli, elj = Q.popleft()
        if M[eli][elj] == '#':
            continue
        for ni, nj in neighbours(M, eli, elj):
            if M[ni][nj] == '#':
                continue
            if visited[ni][nj]:
                continue
            visited[ni][nj] = True
            Q.append((ni, nj))
            if M[ni][nj] == 'G':
                answer += 1
    return answer


for t in range(T):
    n, m = [int(_) for _ in input().split()]
    M = []
    count_G = 0
    has_B = False
    for i in range(n):
        row = [_ for _ in input()]
        count_G += row.count('G')
        if 'B' in row:
            has_B = True
        M.append(row)

    try:
        if not count_G:
            if M[n-1][m-1] == 'B':
                print('No')
            else:
                print('Yes')
        else:
            for i in range(len(M)):
                for j in range(len(M[0])):
                    if M[i][j] == 'B':
                        for x, y in neighbours(M, i, j):
                            if M[x][y] == '.':
                                M[x][y] = '#'
                            elif M[x][y] == 'G':
                                print('No')
                                raise Found()
            accessible_G = bfs(M, n-1, m-1)
            if accessible_G == count_G:
                print('Yes')
            else:
                print('No')
    except Found:
        pass


t = int(input())
dX = [1,-1,0,0]
dY = [0,0,-1,1]
for _ in range(t):
    n, m = list(map(int, input().split()))
    l = []
    for i in range(n):
        l.append(list(input().strip()))

    gCount = 0
    for i in range(n):
        for j in range(m):
            if l[i][j] == 'G':
                gCount += 1
            elif l[i][j] == 'B':
                for d in range(4):
                    x = i + dX[d]
                    y = j + dY[d]
                    if 0 <= x < n and 0 <= y < m and l[x][y] == '.':
                        l[x][y] = '#'

    visited = [[False] * m for i in range(n)]
    gVisit = 0
    stack = []
    if l[n-1][m-1] != '#':
        stack.append((n-1,m-1))
        visited[n-1][m-1] = True
    works = True
    while stack:
        nexX, nexY = stack.pop()
        c = l[nexX][nexY]
        if c == 'G':
            gVisit += 1
        elif c == 'B':
            works = False
            break

        for d in range(4):
            x = nexX + dX[d]
            y = nexY + dY[d]
            if 0 <= x < n and 0 <= y < m and l[x][y] != '#' and not visited[x][y]:
                visited[x][y] = True
                stack.append((x,y))
    if works and gVisit == gCount:
        print('Yes')
    else:
        print('No')
            
            
    


from math import *

def r1(t):
    return t(input())

def r2(t):
    return [t(i) for i in input().split()]

def r3(t):
    return [t(i) for i in input()]

g = []
def dfs(i, j, n, m):
    if g[i][j] == '#':
        return 0
    ans = 0
    if g[i][j] == 'G':
        ans += 1
    if g[i][j] == 'B':
        return -100000
    g[i][j] = '#'
    if (i > 0):
        ans += dfs(i - 1, j, n, m)
    if (i < n - 1):
        ans += dfs(i + 1, j, n, m)
    if (j > 0):
        ans += dfs(i, j - 1, n, m)
    if (j < m - 1):
        ans += dfs(i, j + 1, n, m)
    return ans

for _ in range(r1(int)):
    n, m = r2(int)
    g = []
    used = []
    for i in range(n):
        g.append(r3(str))
        
    cnt = 0
    for i in range(n):
        for j in range(m):
            if g[i][j] == 'B':
                if (i > 0) and g[i-1][j] == '.':
                    g[i-1][j] = '#'
                if (i < n - 1)and g[i+1][j] == '.':
                    g[i+1][j] = '#'
                if (j > 0)and g[i][j-1] == '.':
                    g[i][j-1] = '#'
                if (j < m - 1)and g[i][j + 1] == '.':
                    g[i][j+1] = '#'
            elif g[i][j] == 'G':
                cnt += 1
    #print(cnt)
    if (dfs(n - 1, m - 1, n, m) == cnt):
        print('Yes')
    else:
        print('No')
                


import sys
input=lambda:sys.stdin.readline().rstrip('\n')
D = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def case():
	n, m = list(map(int, input().split()))
	M = [list(input()) for _ in range(n)]

	good = set()
	for y in range(n):
		for x in range(m):
			c = M[y][x]
			if c == 'G':
				good.add((x, y))
			elif c == 'B':
				for dx, dy in D:
					nx = x + dx
					ny = y + dy
					if nx < 0 or ny < 0 or nx >= m or ny >= n:
						continue

					if M[ny][nx] == 'G':
						print('No')
						return
					elif M[ny][nx] != 'B':
						M[ny][nx] = '#'

	if M[-1][-1] == '#':
		print('No' if good else 'Yes')
		return

	V = [[False] * m for _ in range(n)]
	V[n-1][m-1] = True
	Q = [(m-1, n-1)]
	while Q:
		x, y = Q.pop()

		good.discard((x, y))
		for dx, dy in D:
			nx = x + dx
			ny = y + dy

			if nx < 0 or ny < 0 or nx >= m or ny >= n: continue
			if M[ny][nx] == '#' or V[ny][nx]: continue
			V[ny][nx] = True
			Q.append((nx, ny))

	print('Yes' if not good else 'No')

for _ in range(int(input())):
	case()


import sys
strings = iter(sys.stdin.read().split())
ints = (int(x) for x in strings)
sys.setrecursionlimit(3000)

def block(m,R,C,esc,r,c):
    if esc[r][c]==0:
        return 1
    q = [(r,c)]
    h = set([(r,c)])
    while q:
        r,c = q.pop()
        if m[r][c]=='.':
            m[r][c]='#'
        if m[r][c]!='#' and r==R-1 and c==C-1:
            return 0
        if m[r][c]!='#':
            for r,c in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
                if 0<=r<R and 0<=c<C and (r,c) not in h:
                    q.append((r,c))
                    h.add((r,c))
    for r,c in h:
        esc[r][c] = 0
    return 1

def reachability(m,R,C):
    esc = [[0 for c in range(C)] for r in range(R)]
    q = [(R-1,C-1)]
    while q:
        r,c = q.pop()
        esc[r][c] = 1
        if m[r][c]!='#':
            for r,c in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
                if 0<=r<R and 0<=c<C and esc[r][c]==0:
                    q.append((r,c))
    return esc

def main():
    ntc = next(ints)
    for tc in range(1,ntc+1):
        R,C = (next(ints) for i in range(2))
        m = [list(next(strings)) for r in range(R)]
        B = [(r,c) for r in range(R) for c in range(C) if m[r][c]=='B']
        G = [(r,c) for r in range(R) for c in range(C) if m[r][c]=='G']
        esc = reachability(m,R,C)
        ans = all(esc[r][c] for r,c in G)
        if ans:
            ans = all(block(m,R,C,esc,r,c) for r,c in B)
        if ans:
            esc = reachability(m,R,C)
            ans = all(esc[r][c] for r,c in G)
        print('Yes' if ans else 'No')
    return

main()


import sys
input = sys.stdin.readline
t=int(input())
ans=[]
for _ in range(t):
	h,w=map(int,input().split())
	grid=[list(input()) for _ in range(h)]
	good=set()
	bad=set()
	delta=[(-1,0),(1,0),(0,1),(0,-1)]
	for i in range(h):
		for j in range(w):
			if grid[i][j]=="G":
				good.add((i,j))
			elif grid[i][j]=="B":
				bad.add((i,j))
	if not good:
		ans.append("Yes")
		continue
	flg=0
	for ci,cj in bad:
		for di,dj in delta:
			ni,nj=ci+di,cj+dj
			if 0<=ni<h and 0<=nj<w:
				if grid[ni][nj]==".":
					grid[ni][nj]="#"
				elif grid[ni][nj]=="G":
					flg=1
					break
		if flg:
			break
	if flg or grid[h-1][w-1]=="#":
		ans.append("No")
		continue
	q=[(h-1,w-1)]
	vis=[[0]*w for _ in range(h)]
	vis[-1][-1]=1
	while q:
		ci,cj=q.pop()
		for di,dj in delta:
			ni,nj=ci+di,cj+dj
			if 0<=ni<h and 0<=nj<w and grid[ni][nj]!="#" and not vis[ni][nj]:
				vis[ni][nj]=1
				q.append((ni,nj))
	if all(vis[i][j] for i,j in good):
		ans.append("Yes")
	else:
		ans.append("No")
print("\n".join(ans))

q = int(input())
for _ in range(q):
	r,c = list(map(int,input().split()))
	def nbr(x,y):
		out = []
		if x < r-1:
			out.append([x+1,y])
		if x > 0:
			out.append([x-1,y])
		if y > 0:
			out.append([x,y-1])
		if y < c-1:
			out.append([x,y+1])
		return out
	mat = [list(input()) for i in range(r)]
	#print(mat)
	for x in range(r):
		for y in range(c):
			if mat[x][y] == 'B':
				for p in nbr(x,y):
					if mat[p[0]][p[1]] != 'G' and mat[p[0]][p[1]] != 'B':
						mat[p[0]][p[1]] = '#'
	zaj = {}
	for x in range(r):
		for y in range(c):
			zaj[(x,y)] = 0
	if mat[r-1][c-1] == '#':
		su = 0
		for i in range(r):
			su += mat[i].count('G')
		if su == 0:
			print("Yes")
		else:
			print("No")
	else:
		zaj[(r-1,c-1)] = 1
		def dupa(v):
			q = [v]
			while q:
				w = q.pop(0)
				for u in nbr(w[0],w[1]):
					if mat[u[0]][u[1]] != '#':
						if zaj[tuple(u)] == 0:
							q.append(tuple(u))
							zaj[tuple(u)] = 1
		dupa((r-1,c-1))
		#print(zaj)
		dasie = True
		for x in range(r):
			for y in range(c):
				if mat[x][y] == 'B' and zaj[(x,y)] == 1:
					dasie = False
				if mat[x][y] == 'G' and zaj[(x,y)] == 0:
					dasie = False
		if dasie:
			print("Yes")
		else:
			print("No")