Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef has fallen into the Labyrinth!

Fortunately, Chef found a map of the Labyrinth. On this map, the Labyrinth is represented as an N × M grid of integers. The rows of the grid are numbered 1 through N and the columns are numbered 1 through M; let's denote the cell in the i-th row and j-th column by (i, j). Each cell of this grid belongs to one of the following three types:

Forbidden cell (represented by -1). It's impossible to enter or exit this cell. 
Empty cell (represented by 0). Chef can freely enter or exit this cell, but cannot use it to escape the Labyrinth. 
Exit cell (represented by a positive integer x). Chef can freely enter or exit this cell. Moreover, Chef can escape the Labyrinth if he's located in this cell and no more than x seconds have elapsed since the beginning.

Chef is able to move from his current cell to any non-forbidden adjacent cell of the Labyrinth; this action takes one second. Two cells are considered adjacent if they share an edge.

Chef does not even know his starting location, so he decided first to determine his chances of escaping from each possible cell. Specifically, for each non-forbidden cell, Chef wants to know whether it is possible to escape the Labyrinth when he's initially (at time 0) located in this cell.

Help Chef — for each cell, find out if it's possible to start in this cell at time 0 and escape the Labyrinth.

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M.
N lines follow; each of these lines contains M space-separated integers. For each 1 ≤ i ≤ N, 1 ≤ j ≤ M, the j-th number on the i-th of these lines describes the type of cell (i, j) of the Labyrinth.

------ Output ------ 

For each test case, print N lines; each of these lines should contain a string consisting of M characters. The j-th character in the i-th of these strings should be:

B if the cell (i, j) is forbidden 
Y if the cell (i, j) of the Labyrinth is not forbidden and it is possible to escape the Labyrinth when starting in this cell
N if the cell (i, j) is not forbidden and it is impossible to escape when starting in this cell

------ Constraints ------ 

$1 ≤ T ≤ 30$
$1 ≤ N, M ≤ 1,000$
$1 ≤ sum of N · M for all test cases  ≤ 3,000,000$
$-1 ≤ type of each cell ≤ 1,000$

------ Subtasks ------ 

Subtask #1 (30 points):

$2 ≤ N, M ≤ 100$
$1 ≤ sum of N · M for all test cases ≤ 30,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2
5 5
0 0 0 -1 5
0 0 0 -1 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
3 4
0 0 5 -1
0 -1 -1 0
0 0 0 0
----- Sample Output 1 ------ 
NNNBY
YNYBY
YYYYY
YNYYY
NNNYY
YYYB
YBBN
YYNN

Difficulty: HARD
Tags: Graph algorithms

Data structures

Graph traversal
Skill types: Data structures

Starter code:

Solutions:
T = int(input())
for _ in range(T):
	(H, W) = [int(x) for x in input().split()]
	A = [input().split() for row in range(H)]
	exits = [(R, C, int(A[R][C])) for R in range(H) for C in range(W) if A[R][C] != '0' and A[R][C] != '-1']
	B = [[False if A[R][C] != '-1' else True for C in range(W)] for R in range(H)]
	if len(exits) == 0:
		for row in F:
			print(''.join(row))
	exits.sort(key=lambda x: x[2], reverse=True)
	tilesToCheck = set()
	for timeLeft in range(0, exits[0][2] + 1)[::-1]:
		while len(exits) > 0 and exits[0][2] == timeLeft:
			newExit = exits.pop(0)
			(R, C, Q) = newExit
			tilesToCheck.add((R, C))
			B[R][C] = True
		tilesToCheckNextStep = set()
		for tileToCheck in tilesToCheck:
			(R, C) = tileToCheck
			if R != 0 and (not B[R - 1][C]):
				tilesToCheckNextStep.add((R - 1, C))
			if C != W - 1 and (not B[R][C + 1]):
				tilesToCheckNextStep.add((R, C + 1))
			if R != H - 1 and (not B[R + 1][C]):
				tilesToCheckNextStep.add((R + 1, C))
			if C != 0 and (not B[R][C - 1]):
				tilesToCheckNextStep.add((R, C - 1))
			B[R][C] = True
		tilesToCheck = tilesToCheckNextStep
	for R in range(H):
		for C in range(W):
			if B[R][C] == True:
				B[R][C] = 'Y'
			elif B[R][C] == False:
				B[R][C] = 'N'
	for R in range(H):
		for C in range(W):
			if A[R][C] == '-1':
				B[R][C] = 'B'
	for row in B:
		print(''.join(row))