In Chefland, there is a monthly robots competition. In the competition, a grid table of N rows and M columns will be used to place robots. A cell at row i and column j in the table is called cell (i, j). To join this competition, each player will bring two robots to compete and each robot will be placed at a cell in the grid table. Both robots will move at the same time from one cell to another until they meet at the same cell in the table. Of course they can not move outside the table. Each robot has a movable range. If a robot has movable range K, then in a single move, it can move from cell (x, y) to cell (i, j) provided (|i-x| + |j-y| <= K). However, there are some cells in the table that the robots can not stand at, and because of that, they can not move to these cells. The two robots with the minimum number of moves to be at the same cell will win the competition.

Chef plans to join the competition and has two robots with the movable range K1 and K2, respectively. Chef does not know which cells in the table will be used to placed his 2 robots, but he knows that there are 2 cells (1, 1) and (1, M) that robots always can stand at. Therefore, he assumes that the first robot is at cell (1, 1) and the other is at cell (1, M). Chef wants you to help him to find the minimum number of moves that his two robots needed to be at the same cell and promises to give you a gift if he wins the competition. 

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
-  The first line of each test case contains 4 space-separated integers N M K1 K2 denoting the number of rows and columns in the table and the movable ranges of the first and second robot of Chef.
-  The next N lines, each line contains M space-separated numbers either 0 or 1 denoting whether the robots can move to this cell or not (0 means robots can move to this cell, 1 otherwise). It makes sure that values in cell (1, 1) and cell (1, M) are 0.

-----Output-----
For each test case, output a single line containing the minimum number of moves that Chef’s 2 robots needed to be at the same cell. If they can not be at the same cell, print -1.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N, M ≤ 100
- 0 ≤ K1, K2 ≤ 10

----- Subtasks -----
Subtask #1 : (25 points) 
-  K1 = K2 = 1 

Subtask # 2 : (75 points) 
Original Constraints

-----Example-----
Input:
2
4 4 1 1
0 1 1 0
0 1 1 0
0 1 1 0
0 0 0 0
4 4 1 1
0 1 1 0
0 1 1 0
0 1 1 0
1 0 0 1

Output:
5
-1

-----Explanation-----
Example case 1. Robot 1 can move (1, 1) -> (2, 1) -> (3, 1) -> (4, 1) -> (4, 2) -> (4, 3), and robot 2 can move (1, 4) -> (2, 4) -> (3, 4) -> (4, 4) -> (4, 3) -> (4, 3), they meet at cell (4, 3) after 5 moves.
Example case 2. Because the movable range of both robots is 1, robot 1 can not move from (3, 1) to (4, 2), and robot 2 can not move from (3, 4) to (4, 3. Hence, they can not meet each other.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys

def spaces(a, n, m, k, visit1, visit2, dist, position):
	queue = [position]
	lastedit = []
	dist[position[0]][position[1]] = 0
	while queue != []:
		point = queue[0]
		i = point[0]
		j = point[1]
		if visit1[i][j] == False:
			visit1[i][j] = True
			startx = max(i - k, 0)
			endx = min(i + k, n - 1)
			for x in range(startx, endx + 1):
				starty = max(0, j + abs(x - i) - k)
				endy = min(m - 1, j - abs(x - i) + k)
				for y in range(starty, endy + 1):
					if a[x][y] == 0 and visit1[x][y] == False:
						if visit2[x][y] == True:
							lastedit.append([x, y])
						if dist[x][y] > dist[i][j] + 1:
							dist[x][y] = dist[i][j] + 1
							queue.append([x, y])
		queue = queue[1:]
	return lastedit
for t in range(int(input())):
	(n, m, k1, k2) = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	value = sys.maxsize
	listing = []
	visit1 = [[False for i in range(m)] for j in range(n)]
	visit2 = [[False for i in range(m)] for j in range(n)]
	dist1 = [[sys.maxsize for i in range(m)] for j in range(n)]
	dist2 = [[sys.maxsize for i in range(m)] for j in range(n)]
	if k1 >= k2:
		spaces(a, n, m, k1, visit1, visit2, dist1, [0, 0])
	else:
		spaces(a, n, m, k2, visit1, visit2, dist1, [0, m - 1])
		listing = spaces(a, n, m, k1, visit2, visit1, dist2, [0, 0])
	if k1 > k2:
		listing = spaces(a, n, m, k2, visit2, visit1, dist2, [0, m - 1])
	if k1 == k2:
		if dist1[0][m - 1] == sys.maxsize:
			print('-1')
		else:
			print(int((dist1[0][m - 1] + 1) / 2))
	else:
		d = len(listing)
		for i in range(d - 1, -1, -1):
			x = listing[i][0]
			y = listing[i][1]
			if visit1[x][y] == True and dist2[x][y] < value:
				value = dist2[x][y]
		if value != sys.maxsize:
			print(value)
		else:
			print('-1')


from queue import Queue

def run_bfs(x, y, k1, a):
	visited = []
	n = len(a)
	m = len(a[0])
	inf = float('inf')
	for i in range(0, n):
		visited = visited + [[inf] * m]
	visited[x][y] = 0
	qu = Queue()
	qu.put((x, y, 0))
	while not qu.empty():
		(x1, y1, a1) = qu.get()
		for x_n in range(max(x1 - k1, 0), min(x1 + k1 + 1, n)):
			t1 = abs(x_n - x1)
			for y_n in range(max(y1 - k1 + t1, 0), min(y1 + k1 - t1 + 1, m)):
				if a[x_n][y_n] == 0:
					if visited[x_n][y_n] == inf:
						visited[x_n][y_n] = a1 + 1
						qu.put((x_n, y_n, a1 + 1))
	return visited
t = eval(input())
for i in range(0, t):
	inp = input()
	inp = [int(j) for j in inp.split()]
	[n, m, k1, k2] = inp
	a = []
	for t1 in range(0, n):
		inp = input()
		inp = [int(j) for j in inp.split()]
		a = a + [inp]
	visited1 = run_bfs(0, 0, k1, a)
	visited2 = run_bfs(0, m - 1, k2, a)
	m1 = float('inf')
	for x in range(0, n):
		for y in range(0, m):
			m_l = max(visited1[x][y], visited2[x][y])
			m1 = min(m_l, m1)
	if m1 < float('inf'):
		print(m1)
	else:
		print('-1')


import sys
sys.setrecursionlimit(10000000)
flag = []

def isSafe(l, x, y, n, m):
	if x >= 0 and x < n and (y >= 0) and (y < m) and (l[x][y] == 0):
		return True
	return False

def solveMaze(l, n, m):
	x = solveMazeUtil(l, n, m, 0, 0, 0)
	return x

def solveMazeUtil(l, n, m, x, y, count):
	nonlocal flag
	count += 1
	if x == 0 and y == m - 1:
		if l[x][y] == 0:
			return count
		return -1
	if isSafe(l, x, y, n, m) == True:
		if flag[x][y] == 0:
			flag[x][y] = 1
			z = solveMazeUtil(l, n, m, x - 1, y, count)
			if z != -1:
				return z
			z = solveMazeUtil(l, n, m, x, y - 1, count)
			if z != -1:
				return z
			z = solveMazeUtil(l, n, m, x, y + 1, count)
			if z != -1:
				return z
			z = solveMazeUtil(l, n, m, x + 1, y, count)
			if z != -1:
				return z
			return -1
	return -1

def main():
	nonlocal flag
	for q in range(eval(input())):
		a = [int(i) for i in input().split()]
		n = a[0]
		m = a[1]
		l = []
		if a[2] == 0 and a[3] == 0:
			print(-1)
		else:
			flag = [[0 for i in range(m)] for j in range(n)]
			for i in range(n):
				l.append([int(i) for i in input().split()])
			ans = solveMaze(l, n, m)
			if a[2] == 0 or a[3] == 0:
				print(ans)
			elif ans >= 0:
				print(ans / 2)
			else:
				print(ans)
main()


from heapq import heappush, heappop
import sys

def getDistancesBot1(a, n, m, mat, k):
	for i in range(n):
		mat.append([20000 for j in range(m)])
	heap = []
	mat[0][0] = 0
	heappush(heap, (0, 0, 0))
	while len(heap) != 0:
		item = heappop(heap)
		top = max(0, item[2] - k)
		bottom = min(n - 1, item[2] + k)
		for y in range(top, bottom + 1):
			c = k - abs(y - item[2])
			left = max(0, item[1] - c)
			right = min(m - 1, item[1] + c)
			for x in range(left, right + 1):
				if a[y][x] == 0:
					if mat[y][x] > item[0] + 1:
						mat[y][x] = item[0] + 1
						heappush(heap, (mat[y][x], x, y))

def getDistancesBot2(a, n, m, mat, k):
	for i in range(n):
		mat.append([20000 for j in range(m)])
	heap = []
	mat[0][m - 1] = 0
	heappush(heap, (0, m - 1, 0))
	while len(heap) != 0:
		item = heappop(heap)
		top = max(0, item[2] - k)
		bottom = min(n - 1, item[2] + k)
		for y in range(top, bottom + 1):
			c = k - abs(y - item[2])
			left = max(0, item[1] - c)
			right = min(m - 1, item[1] + c)
			for x in range(left, right + 1):
				if a[y][x] == 0:
					if mat[y][x] > item[0] + 1:
						mat[y][x] = item[0] + 1
						heappush(heap, (mat[y][x], x, y))
t = int(input().strip())
for i in range(t):
	[n, m, k1, k2] = list(map(int, input().strip().split(' ')))
	arr = []
	for j in range(n):
		arr.append(list(map(int, input().strip().split(' '))))
	mat1 = []
	mat2 = []
	getDistancesBot1(arr, n, m, mat1, k1)
	getDistancesBot2(arr, n, m, mat2, k2)
	minSteps = 2000
	for x in range(n):
		for y in range(m):
			minSteps = min(minSteps, max(mat1[x][y], mat2[x][y]))
	if minSteps == 2000:
		print(-1)
	else:
		print(minSteps)