You are given a grid with $n$ rows and $m$ columns. We denote the square on the $i$-th ($1\le i\le n$) row and $j$-th ($1\le j\le m$) column by $(i, j)$ and the number there by $a_{ij}$. All numbers are equal to $1$ or to $-1$.

You start from the square $(1, 1)$ and can move one square down or one square to the right at a time. In the end, you want to end up at the square $(n, m)$.

Is it possible to move in such a way so that the sum of the values written in all the visited cells (including $a_{11}$ and $a_{nm}$) is $0$?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 1000$)  — the size of the grid.

Each of the following $n$ lines contains $m$ integers. The $j$-th integer on the $i$-th line is $a_{ij}$ ($a_{ij} = 1$ or $-1$)  — the element in the cell $(i, j)$.

It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $10^6$.


-----Output-----

For each test case, print "YES" if there exists a path from the top left to the bottom right that adds up to $0$, and "NO" otherwise. You can output each letter in any case.


-----Examples-----

Input
5
1 1
1
1 2
1 -1
1 4
1 -1 1 -1
3 4
1 -1 -1 -1
-1 1 1 -1
1 1 1 -1
3 4
1 -1 1 1
-1 1 -1 1
1 -1 1 1
Output
NO
YES
YES
YES
NO


-----Note-----

One possible path for the fourth test case is given in the picture in the statement.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Shortest paths

Complete search

Greedy algorithms

Dynamic programming

Data structures


Solutions:
for case in range(int(input())):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for _ in range(n)]
	if (n + m - 1) % 2:
		print('NO')
		continue
	dp = [0] * (m + 1)
	for i in range(n):
		dp[0] = int(not i)
		for j in range(m):
			dp[j + 1] = (dp[j] | dp[j + 1]) << (a[i][j] == -1)
	if dp[-1] & 1 << (n + m - 1) // 2:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for i in range(n)]
	if (n + m) % 2 == 0:
		print('NO')
	else:
		g = [[0] * m for i in range(n)]
		g[0][0] = 1 << (a[0][0] == -1)
		for j in range(1, m):
			g[0][j] = g[0][j - 1] << (a[0][j] == -1)
		for i in range(1, n):
			g[i][0] = g[i - 1][0] << (a[i][0] == -1)
			for j in range(1, m):
				g[i][j] = (g[i - 1][j] | g[i][j - 1]) << (a[i][j] == -1)
		if g[n - 1][m - 1] & 1 << (n + m - 1) // 2 == 0:
			print('NO')
		else:
			print('YES')


p = int(input())
for _ in range(p):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for i in range(n)]
	if (n + m) % 2 == 0:
		print('NO')
	else:
		k = [[0] * m for i in range(n)]
		k[0][0] = 1 << (a[0][0] == -1)
		for j in range(1, m):
			k[0][j] = k[0][j - 1] << (a[0][j] == -1)
		for i in range(1, n):
			k[i][0] = k[i - 1][0] << (a[i][0] == -1)
			for j in range(1, m):
				k[i][j] = (k[i - 1][j] | k[i][j - 1]) << (a[i][j] == -1)
		if k[n - 1][m - 1] & 1 << (n + m - 1) // 2 == 0:
			print('NO')
		else:
			print('YES')


(inp, r, p) = (input, range, print)
I = lambda : map(int, input().split())
for _1 in r(int(inp())):
	(n, m) = I()
	inp_mat = [list(I()) for _2 in r(n)]
	a = [[0 for _ in r(m)] for _ in r(n)]
	if (n + m - 1) % 2 == 1:
		p('NO')
		continue
	a[0][0] = 1 << (inp_mat[0][0] != 1)
	for j in r(1, m):
		a[0][j] = a[0][j - 1] << (inp_mat[0][j] == -1)
	for i in r(1, n):
		a[i][0] = a[i - 1][0] << (inp_mat[i][0] != 1)
		for j in r(1, m):
			a[i][j] = (a[i - 1][j] | a[i][j - 1]) << (inp_mat[i][j] != 1)
	p(['NO', 'YES'][1 if a[n - 1][m - 1] & 1 << (m + n - 1) // 2 else 0])


input = __import__('sys').stdin.readline

def solve():
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	dp = []
	total = 0
	for x in a:
		total += 1 if x == 1 else 0
		dp.append((total, total))
	for _ in range(1, n):
		a = list(map(int, input().split()))
		c = 1 if a[0] == 1 else 0
		newdp = [(dp[0][0] + c, dp[0][1] + c)]
		for i in range(1, m):
			c = 1 if a[i] == 1 else 0
			newdp.append((min(dp[i][0], newdp[i - 1][0]) + c, max(dp[i][1], newdp[i - 1][1]) + c))
		dp = newdp
	print('YES' if (n + m - 1) % 2 == 0 and dp[m - 1][0] <= (n + m - 1) // 2 <= dp[m - 1][1] else 'NO')
for _ in range(int(input())):
	solve()


import sys
from collections import deque
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	arr = [list(map(int, input().split())) for _ in range(n)]
	if (n + m) % 2 == 0:
		return 'NO'
	dp = [[-float('inf'), float('inf')] for _ in range(m)]
	for i in range(n):
		for j in range(m):
			if j == 0:
				dp[j][0] = arr[i][j] if i == 0 else dp[j][0] + arr[i][j]
				dp[j][1] = arr[i][j] if i == 0 else dp[j][1] + arr[i][j]
			else:
				dp[j][0] = max(dp[j][0], dp[j - 1][0]) + arr[i][j]
				dp[j][1] = min(dp[j][1], dp[j - 1][1]) + arr[i][j]
	return 'YES' if dp[-1][1] <= 0 <= dp[-1][0] else 'NO'
for _ in range(int(input())):
	print(solve())


def solve():
	(n, m) = map(int, input().split())
	arr = [list(map(int, input().split())) for _ in range(n)]
	if (n + m) % 2 == 0:
		return 'NO'
	dp = [[-float('inf'), float('inf')] for _ in range(m)]
	for i in range(n):
		for j in range(m):
			if j == 0:
				dp[j][0] = arr[i][j] if i == 0 else dp[j][0] + arr[i][j]
				dp[j][1] = arr[i][j] if i == 0 else dp[j][1] + arr[i][j]
			else:
				dp[j][0] = max(dp[j][0], dp[j - 1][0]) + arr[i][j]
				dp[j][1] = min(dp[j][1], dp[j - 1][1]) + arr[i][j]
	return 'YES' if dp[-1][1] <= 0 <= dp[-1][0] else 'NO'
for _ in range(int(input())):
	print(solve())


def main():
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	if (n + m) % 2 == 0:
		print('NO')
		return
	b = [[0] * m for _ in range(n)]
	b[0][0] = a[0][0]
	for i in range(1, n):
		b[i][0] = b[i - 1][0] + a[i][0]
	for j in range(1, m):
		b[0][j] = b[0][j - 1] + a[0][j]
	bmin = [i.copy() for i in b]
	for i in range(1, n):
		for j in range(1, m):
			b[i][j] = a[i][j] + max(b[i - 1][j], b[i][j - 1])
			bmin[i][j] = a[i][j] + min(bmin[i - 1][j], bmin[i][j - 1])
	if bmin[-1][-1] <= 0 <= b[-1][-1]:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	main()


t = int(input())
for _ in range(t):
	(m, n) = list(map(int, input().split()))
	a = []
	for _ in range(m):
		a.append(list(map(int, input().split())))
	if (m + n) % 2 == 0:
		print('NO')
		continue
	mn = [0] * n
	mn[0] = a[0][0]
	for j in range(1, n):
		mn[j] = mn[j - 1] + a[0][j]
	mx = mn[:]
	for i in range(1, m):
		mn[0] += a[i][0]
		mx[0] += a[i][0]
		for j in range(1, n):
			mn[j] = min(mn[j], mn[j - 1]) + a[i][j]
			mx[j] = max(mx[j], mx[j - 1]) + a[i][j]
	print('NO') if mx[-1] < 0 or mn[-1] > 0 else print('YES')


def f(arr, m, n, mx, mi):
	mx[m][n] = mi[m][n] = arr[m][n]
	for i in range(m - 1, -1, -1):
		mx[i][n] = mi[i][n] = arr[i][n] + mx[i + 1][n]
	for i in range(n - 1, -1, -1):
		mx[m][i] = mi[m][i] = arr[m][i] + mx[m][i + 1]
	for i in range(m - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			mx[i][j] = max(mx[i + 1][j], mx[i][j + 1]) + arr[i][j]
			mi[i][j] = min(mi[i + 1][j], mi[i][j + 1]) + arr[i][j]
	return
t = int(input())
for _ in range(t):
	(m, n) = map(int, input().split())
	arr = []
	ans = True
	for i in range(m):
		ar = list(map(int, input().split()))
		arr.append(ar)
	if (m + n) % 2 == 0:
		ans = False
	else:
		mx = [[-1 for i in range(n)] for j in range(m)]
		mi = [[-1 for i in range(n)] for j in range(m)]
		f(arr, m - 1, n - 1, mx, mi)
		a = mx[0][0]
		b = mi[0][0]
		if a < 0 or b > 0:
			ans = False
	if ans:
		print('YES')
	else:
		print('NO')


import sys
t = int(input())
for _ in range(t):
	(m, n) = list(map(int, input().split()))
	matrix = []
	for r in range(m):
		matrix.append(list(map(int, input().split())))
	if (m + n) % 2 == 0:
		print('NO')
		continue
	mn = [0] * n
	mn[0] = matrix[0][0]
	for i in range(1, n):
		mn[i] += mn[i - 1] + matrix[0][i]
	mx = mn[:]
	for r in matrix[1:]:
		mn[0] += r[0]
		mx[0] += r[0]
		for (j, x) in enumerate(r[1:]):
			mn[j + 1] = min(mn[j + 1], mn[j]) + x
			mx[j + 1] = max(mx[j + 1], mx[j]) + x
	print('NO') if mn[-1] > 0 or mx[-1] < 0 else print('YES')


for _ in [0] * int(input()):
	(n, m) = map(int, input().split())
	a = [[*map(int, input().split())] for x in [0] * n]
	dp = [[0] * m for x in [0] * n]
	dp[0][0] = a[0][0]
	for i in range(1, n):
		dp[i][0] = dp[i - 1][0] + a[i][0]
	for i in range(1, m):
		dp[0][i] = dp[0][i - 1] + a[0][i]
	for i in range(1, n):
		for j in range(1, m):
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j]
	maxi = dp[-1][-1]
	dp = [[0] * m for x in [0] * n]
	dp[0][0] = a[0][0]
	for i in range(1, n):
		dp[i][0] = dp[i - 1][0] + a[i][0]
	for i in range(1, m):
		dp[0][i] = dp[0][i - 1] + a[0][i]
	for i in range(1, n):
		for j in range(1, m):
			dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j]
	mini = dp[-1][-1]
	print('NYOE S'[(m + n) % 2 and mini <= 0 <= maxi::2])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for _ in range(n)]
	if (n + m) % 2 == 0:
		print('NO')
	else:
		maxi = [[0] * m for i in range(n)]
		mini = [[0] * m for i in range(n)]
		maxi[0][0] = mini[0][0] = a[0][0]
		for j in range(1, m):
			maxi[0][j] = mini[0][j] = maxi[0][j - 1] + a[0][j]
		for i in range(1, n):
			maxi[i][0] = mini[i][0] = maxi[i - 1][0] + a[i][0]
		for i in range(1, n):
			for j in range(1, m):
				maxi[i][j] = max(maxi[i - 1][j], maxi[i][j - 1]) + a[i][j]
				mini[i][j] = min(mini[i - 1][j], mini[i][j - 1]) + a[i][j]
		if maxi[n - 1][m - 1] < 0 or mini[n - 1][m - 1] > 0:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	g = []
	for i in range(n):
		g.append(list(map(int, input().split())))
	dp1 = [[0] * m for j in range(n)]
	dp2 = [[0] * m for j in range(n)]
	c = 0
	for i in range(n):
		c += g[i][0]
		dp1[i][0] = c
		dp2[i][0] = c
	c = 0
	for i in range(m):
		c += g[0][i]
		dp2[0][i] = c
		dp1[0][i] = c
	for i in range(1, n):
		for j in range(1, m):
			dp1[i][j] = min(dp1[i - 1][j], dp1[i][j - 1]) + g[i][j]
			dp2[i][j] = max(dp2[i - 1][j], dp2[i][j - 1]) + g[i][j]
	if dp1[-1][-1] % 2 == 1 or dp1[-1][-1] > 0 or dp2[-1][-1] < 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		items = list(map(int, input().split()))
		arr.append(items)
	if (n + m) % 2 == 0:
		print('NO')
		continue
	minmax = [[0] * m for i in range(n)]
	minmax[0][0] = arr[0][0]
	for i in range(1, m):
		minmax[0][i] = minmax[0][i - 1] + arr[0][i]
	for i in range(1, n):
		minmax[i][0] = minmax[i - 1][0] + arr[i][0]
	for i in range(1, n):
		for j in range(1, m):
			minmax[i][j] = max(minmax[i - 1][j], minmax[i][j - 1]) + arr[i][j]
	if minmax[n - 1][m - 1] < 0:
		print('NO')
	else:
		for i in range(1, n):
			for j in range(1, m):
				minmax[i][j] = min(minmax[i - 1][j], minmax[i][j - 1]) + arr[i][j]
		if minmax[n - 1][m - 1] <= 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	grid = []
	for i in range(n):
		grid.append(list(map(int, input().split())))
	if (n + m - 1) % 2 != 0:
		print('NO')
		continue
	min_path = [[0 for i in range(m)] for j in range(n)]
	max_path = [[0 for i in range(m)] for j in range(n)]
	min_path[n - 1][m - 1] = max_path[n - 1][m - 1] = grid[n - 1][m - 1]
	for i in range(m - 2, -1, -1):
		min_path[n - 1][i] = max_path[n - 1][i] = min_path[n - 1][i + 1] + grid[n - 1][i]
	for i in range(n - 2, -1, -1):
		min_path[i][m - 1] = max_path[i][m - 1] = min_path[i + 1][m - 1] + grid[i][m - 1]
	for i in range(n - 2, -1, -1):
		for j in range(m - 2, -1, -1):
			min_path[i][j] = min(min_path[i + 1][j], min_path[i][j + 1]) + grid[i][j]
			max_path[i][j] = max(max_path[i + 1][j], max_path[i][j + 1]) + grid[i][j]
	if min_path[0][0] <= 0 <= max_path[0][0]:
		print('YES')
	else:
		print('NO')


import sys

def solve():
	inp = sys.stdin.readline
	(n, m) = map(int, inp().split())
	a = [list(map(int, inp().split())) for i in range(n)]
	if (n + m - 1) % 2 != 0:
		print('NO')
		return
	b = [[0] * m for i in range(n)]
	c = [[0] * m for i in range(n)]
	b[0][0] = max(a[0][0], 0)
	c[0][0] = max(a[0][0], 0)
	d = int(1000000000.0)
	e = -d
	for x in range(n):
		for y in range(m):
			if x != 0 or y != 0:
				z = max(a[x][y], 0)
				if x > 0:
					u = b[x - 1][y] + z
					v = c[x - 1][y] + z
				else:
					u = d
					v = e
				if y > 0:
					u = min(u, b[x][y - 1] + z)
					v = max(v, c[x][y - 1] + z)
				b[x][y] = u
				c[x][y] = v
	z = (n + m - 1) // 2
	if z >= b[n - 1][m - 1] and z <= c[n - 1][m - 1]:
		print('YES')
	else:
		print('NO')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


time = int(input())
while time:
	time -= 1
	(n, m) = [int(x) for x in input().split()]
	arr = [[] for _ in range(n)]
	for i in range(n):
		arr[i] = [int(x) for x in input().split()]
	if (n + m - 1) % 2 == 1:
		print('NO')
		continue
	dpmin = [[0] * m for _ in range(n)]
	dpmax = [[0] * m for _ in range(n)]
	dpmin[0][0] = arr[0][0]
	dpmax[0][0] = arr[0][0]
	for j in range(1, m):
		dpmin[0][j] = dpmin[0][j - 1] + arr[0][j]
		dpmax[0][j] = dpmax[0][j - 1] + arr[0][j]
	for i in range(1, n):
		dpmin[i][0] = dpmin[i - 1][0] + arr[i][0]
		dpmax[i][0] = dpmax[i - 1][0] + arr[i][0]
	for i in range(1, n):
		for j in range(1, m):
			dpmin[i][j] = min(dpmin[i - 1][j], dpmin[i][j - 1]) + arr[i][j]
			dpmax[i][j] = max(dpmax[i - 1][j], dpmax[i][j - 1]) + arr[i][j]
	if dpmin[n - 1][m - 1] <= 0 and 0 <= dpmax[n - 1][m - 1]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(row, col) = map(int, input().split())
	grid = []
	for _ in range(row):
		grid.append(list(map(int, input().split())))
	min_dp = [[0] * col for _ in range(row)]
	max_dp = [[0] * col for _ in range(row)]
	if row + col + 1 & 1:
		print('NO')
		continue
	for i in range(row):
		for j in range(col):
			if i == 0 and j == 0:
				min_dp[i][j] = max_dp[i][j] = grid[i][j]
				continue
			if i and j:
				min_dp[i][j] = grid[i][j] + min(min_dp[i - 1][j], min_dp[i][j - 1])
				max_dp[i][j] = grid[i][j] + max(max_dp[i - 1][j], max_dp[i][j - 1])
			elif i:
				min_dp[i][j] = grid[i][j] + min_dp[i - 1][j]
				max_dp[i][j] = grid[i][j] + max_dp[i - 1][j]
			else:
				min_dp[i][j] = grid[i][j] + min_dp[i][j - 1]
				max_dp[i][j] = grid[i][j] + max_dp[i][j - 1]
	if min_dp[-1][-1] <= 0 <= max_dp[-1][-1]:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		l = list(map(int, input().split()))
		arr.append(l)
	pl = n + m - 1
	if pl % 2 != 0:
		print('NO')
		continue
	(madp, midp) = ([[0 for j in range(m)] for i in range(n)], [[0 for j in range(m)] for i in range(n)])
	(madp[0][0], midp[0][0]) = (arr[0][0], arr[0][0])
	for i in range(1, n):
		(madp[i][0], midp[i][0]) = (arr[i][0] + madp[i - 1][0], arr[i][0] + midp[i - 1][0])
	for j in range(1, m):
		(madp[0][j], midp[0][j]) = (arr[0][j] + madp[0][j - 1], arr[0][j] + midp[0][j - 1])
	for i in range(1, n):
		for j in range(1, m):
			madp[i][j] = arr[i][j] + max(madp[i - 1][j], madp[i][j - 1])
			midp[i][j] = arr[i][j] + min(midp[i - 1][j], midp[i][j - 1])
	if midp[-1][-1] <= 0 <= madp[-1][-1]:
		print('YES')
	else:
		print('NO')


a = int(input())
for k in range(0, a):
	(n, m) = map(int, input().split())
	c = []
	for i in range(0, n):
		c.append(list(map(int, input().split())))
	d_min = [[] for _ in range(n)]
	d_max = [[] for _ in range(n)]
	if (n + m - 1) % 2 == 0:
		d_max[0].append(c[0][0])
		d_min[0].append(c[0][0])
		for j in range(1, m):
			d_max[0].append(d_max[0][j - 1] + c[0][j])
			d_min[0].append(d_min[0][j - 1] + c[0][j])
		for j in range(1, n):
			d_max[j].append(d_max[j - 1][0] + c[j][0])
			d_min[j].append(d_min[j - 1][0] + c[j][0])
		for i in range(1, n):
			for j in range(1, m):
				d_max[i].append(max(d_max[i - 1][j], d_max[i][j - 1]) + c[i][j])
				d_min[i].append(min(d_min[i - 1][j], d_min[i][j - 1]) + c[i][j])
		if d_max[n - 1][m - 1] >= 0 and d_min[n - 1][m - 1] <= 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


from itertools import accumulate
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for __ in range(n):
		a.append(list(map(int, input().split())))
	if (n + m) % 2 == 0:
		print('NO')
		continue
	dp_mn = list(accumulate(a[0]))
	for i in range(1, n):
		for j in range(m):
			if j > 0:
				dp_mn[j] = min(dp_mn[j - 1], dp_mn[j])
			dp_mn[j] += a[i][j]
	dp_mx = list(accumulate(a[0]))
	for i in range(1, n):
		for j in range(m):
			if j > 0:
				dp_mx[j] = max(dp_mx[j - 1], dp_mx[j])
			dp_mx[j] += a[i][j]
	if dp_mn[-1] <= 0 and dp_mx[-1] >= 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	board = []
	minBoard = []
	maxBoard = []
	for i in range(n):
		row = list(map(int, input().split(' ')))
		minRow = [0 for _ in range(m)]
		maxRow = [0 for _ in range(m)]
		board.append(row)
		minBoard.append(minRow)
		maxBoard.append(maxRow)
	if (m + n) % 2 == 0:
		print('NO')
	else:
		minBoard[0][0] = board[0][0]
		maxBoard[0][0] = board[0][0]
		for i in range(1, n):
			minBoard[i][0] = board[i][0] + minBoard[i - 1][0]
			maxBoard[i][0] = board[i][0] + maxBoard[i - 1][0]
		for i in range(1, m):
			minBoard[0][i] = board[0][i] + minBoard[0][i - 1]
			maxBoard[0][i] = board[0][i] + maxBoard[0][i - 1]
		for i in range(1, n):
			for j in range(1, m):
				minBoard[i][j] = board[i][j] + min(minBoard[i - 1][j], minBoard[i][j - 1])
				maxBoard[i][j] = board[i][j] + max(maxBoard[i - 1][j], maxBoard[i][j - 1])
		if minBoard[n - 1][m - 1] <= 0 <= maxBoard[n - 1][m - 1]:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		z = list(map(int, input().split()))
		a.append(z)
	mn = [[0 for i in range(m)] for j in range(n)]
	mx = [[0 for i in range(m)] for j in range(n)]
	mn[0][0] = mx[0][0] = a[0][0]
	for i in range(n):
		for j in range(m):
			if i > 0 and j > 0:
				mn[i][j] = min(mn[i - 1][j], mn[i][j - 1]) + a[i][j]
				mx[i][j] = max(mx[i - 1][j], mx[i][j - 1]) + a[i][j]
			elif i > 0:
				mn[i][j] = mn[i - 1][j] + a[i][j]
				mx[i][j] = mx[i - 1][j] + a[i][j]
			elif j > 0:
				mn[i][j] = mn[i][j - 1] + a[i][j]
				mx[i][j] = mx[i][j - 1] + a[i][j]
	if (m + n) % 2 == 1 and mn[n - 1][m - 1] <= 0 and (mx[n - 1][m - 1] >= 0):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = []
	for x in range(n):
		l.append(list(map(int, input().split())))
	if False:
		print('YES')
	else:
		dpmin = []
		dpmax = []
		mn = []
		mx = []
		for i in range(0, n):
			for j in range(0, m):
				mn.append(1000)
				mx.append(-1000)
			dpmin.append(mn)
			dpmax.append(mx)
			mn = []
			mx = []
		dpmin[0][0] = l[0][0]
		dpmax[0][0] = l[0][0]
		for x in range(1, m):
			dpmin[0][x] = l[0][x] + dpmin[0][x - 1]
			dpmax[0][x] = l[0][x] + dpmax[0][x - 1]
		for x in range(1, n):
			dpmin[x][0] = l[x][0] + dpmin[x - 1][0]
			dpmax[x][0] = l[x][0] + dpmax[x - 1][0]
		for x in range(1, n):
			for y in range(1, m):
				dpmin[x][y] = min(dpmin[x - 1][y], dpmin[x][y - 1]) + l[x][y]
				dpmax[x][y] = max(dpmax[x - 1][y], dpmax[x][y - 1]) + l[x][y]
		if dpmax[n - 1][m - 1] % 2 == 1 or dpmin[n - 1][m - 1] > 0 or dpmax[n - 1][m - 1] < 0:
			print('NO')
		else:
			print('YES')


for q in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	arr = []
	for i in range(n):
		arr.append([int(x) for x in input().split()])
	mn = [[arr[i][j] for j in range(m)] for i in range(n)]
	mx = [[arr[i][j] for j in range(m)] for i in range(n)]
	for i in range(1, m):
		mn[0][i] += mn[0][i - 1]
		mx[0][i] += mx[0][i - 1]
	for i in range(1, n):
		mn[i][0] += mn[i - 1][0]
		mx[i][0] += mx[i - 1][0]
	for i in range(1, n):
		for j in range(1, m):
			mn[i][j] = min(mn[i - 1][j], mn[i][j - 1]) + arr[i][j]
			mx[i][j] = max(mx[i - 1][j], mx[i][j - 1]) + arr[i][j]
	if mn[n - 1][m - 1] <= 0 and mx[n - 1][m - 1] >= 0 and ((m + n - 1) % 2 == 0):
		print('YES')
	else:
		print('NO')


from os import error
import sys
input = sys.stdin.readline
DEBUG = False

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	(n, m) = inlt()
	(mx, pmx) = ([0] * m, [0] * m)
	pmx[0] = 2 ** 1002
	for i in range(n):
		row = inlt()
		for j in range(0, m):
			if j > 0:
				if row[j] == 1:
					mx[j] = pmx[j] * 2 | mx[j - 1] * 2
				else:
					mx[j] = pmx[j] // 2 | mx[j - 1] // 2
			elif row[j] == 1:
				mx[j] = pmx[j] * 2
			else:
				mx[j] = pmx[j] // 2
		pmx = mx
	if pmx[-1] & 2 ** 1002 > 0:
		return 'YES'
	return 'NO'
q = inp()
for t in range(q):
	ans = solve()
	print(ans)


n = int(input())
for i in range(n):
	(ROWS, COLS) = map(int, input().split())
	matrix = []
	for i in range(ROWS):
		matrix.append([int(num) for num in input().split()])
	if (ROWS + COLS) % 2 == 0:
		print('NO')
	else:
		matrix[0][0] = (matrix[0][0], matrix[0][0])
		for col in range(1, COLS):
			minAndMax = matrix[0][col - 1][0] + matrix[0][col]
			matrix[0][col] = (minAndMax, minAndMax)
		for row in range(1, ROWS):
			minAndMax = matrix[row - 1][0][0] + matrix[row][0]
			matrix[row][0] = (minAndMax, minAndMax)
		for row in range(1, ROWS):
			for col in range(1, COLS):
				minn = min(matrix[row - 1][col][0], matrix[row][col - 1][0]) + matrix[row][col]
				maxx = max(matrix[row - 1][col][1], matrix[row][col - 1][1]) + matrix[row][col]
				matrix[row][col] = (minn, maxx)
		if 0 in range(matrix[-1][-1][0], matrix[-1][-1][1] + 1):
			print('YES')
		else:
			print('NO')


def solve(mat):
	if (len(mat) + len(mat[0]) - 1) % 2:
		return False
	dpmin = [[float('INF') for i in range(len(mat[0]))] for j in range(len(mat))]
	dpmax = [[-float('INF') for i in range(len(mat[0]))] for j in range(len(mat))]
	dpmin[0][0] = dpmax[0][0] = mat[0][0]
	for i in range(1, len(mat)):
		dpmin[i][0] = dpmax[i][0] = dpmin[i - 1][0] + mat[i][0]
	for i in range(1, len(mat[0])):
		dpmin[0][i] = dpmax[0][i] = dpmin[0][i - 1] + mat[0][i]
	for i in range(1, len(mat)):
		for j in range(1, len(mat[0])):
			dpmin[i][j] = min(dpmin[i - 1][j], dpmin[i][j - 1]) + mat[i][j]
			dpmax[i][j] = max(dpmax[i - 1][j], dpmax[i][j - 1]) + mat[i][j]
	return dpmin[-1][-1] <= 0 <= dpmax[-1][-1]
t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	mat = []
	for i in range(n):
		mat.append(list(map(int, input().split())))
	if solve(mat):
		print('YES')
	else:
		print('NO')