Read problems statements in [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

You are given a grid with size $N \times M$. Each cell of this grid contains either $0$ or $1$.

We should perform the following operation until the size of the grid becomes $1 \times 1$:
Suppose the present size of the grid is $x \times y$.
Choose one of the $x-1$ horizontal lines or $y-1$ vertical lines crossing the grid.
Fold the grid along this line. For each pair of cells which overlap after this folding, replace them by a single cell such that the value in this cell is the XOR of the values in the two overlapping cells. Thus, we obtain a new grid.

Example: If the initial grid is

000
111
010

1) After folding along $1$-st horizontal line, the grid is

111
010

2) After folding along the $2$-nd vertical line, the grid is

10
01

3) After folding along the $1$-st horizontal line, the grid is

11

4) After folding along the $1$-st vertical line, the grid is

0

Determine whether there is a sequence of folds such that in the final $1 \times 1$ grid, the only cell contains $1$.

------  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. For each valid $i$, the $i$-th of these lines contains a single binary string $S_{i}$ with length $M$ describing the $i$-th row of the grid.

------  Output ------
Print a single line containing the string "YES" if it is possible to obtain $1$ in the final $1 \times 1$ grid or "NO" if it is impossible (without quotes).

You may print each character of the string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

------  Constraints ------
$1 ≤ T ≤ 2 \cdot 10^{4}$
$1 ≤ N \cdot M ≤ 10^{5}$
each character of each string is '0' or '1'
the sum of $N \cdot M$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
2
1 2
01
3 3
000
111
010
----- Sample Output 1 ------ 
YES
NO
----- explanation 1 ------ 
Example case 1: There is only $1$ possible move, which is to fold along the only vertical line. The resulting grid contains only $1$.

Example case 2: There is no sequence of moves which would result in a $1 \times 1$ grid containing only $1$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
from operator import ixor
from functools import reduce
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	arr = 0
	for __ in range(a):
		arr = reduce(ixor, [arr, reduce(ixor, map(int, *map(str, input().split())))])
	if arr:
		print('YES')
	else:
		print('NO')


for z in range(int(input())):
	(n, m) = map(int, input().split())
	count = 0
	for i in range(n):
		s = input()
		count += s.count('1')
	if count % 2 != 0:
		print('YES')
	else:
		print('NO')


def Test(n, m):
	import functools
	arr = []
	for __ in range(n):
		inp = [int(x) for x in input().strip()]
		arr.append(functools.reduce(lambda x, y: x ^ y, inp))
	if functools.reduce(lambda x, y: x ^ y, arr) == 1:
		return 'YES'
	else:
		return 'NO'
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(Test(n, m))


import sys
input = sys.stdin.readline
T = int(input())
for j in range(T):
	(x, y) = map(int, input().split())
	counter = 0
	for i in range(x):
		A = input()
		if A.count('1') % 2:
			counter += 1
	if counter % 2 == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	sum = 0
	for i in range(n):
		s = input()
		for i in s:
			if i == '1':
				sum += 1
	if sum % 2 == 0:
		print('NO')
	else:
		print('YES')


from functools import reduce
k = int(input())
for o in range(k):
	(a, b) = input().split(' ')
	a = int(a)
	b = int(b)
	x = []
	y = []
	for i in range(a):
		x = [int(j) for j in input()]
		r = reduce(lambda c, d: c ^ d, x)
		y.append(r)
	r = reduce(lambda c, d: c ^ d, y)
	if r == 1:
		print('YES')
	else:
		print('NO')


try:
	t = int(input())
	for i in range(t):
		Result_xor = 0
		(N, M) = map(int, input().split())
		arr = []
		for j in range(N):
			arr.append(input())
			for k in range(M):
				Result_xor = Result_xor ^ int(arr[j][k])
		if Result_xor == 1:
			print('YES')
		else:
			print('NO')
except EOFError:
	print()


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	ans = 0
	for i in range(N):
		X = input()
		for j in range(M):
			if X[j] == '1':
				ans += 1
	if ans % 2 == 0:
		print('NO')
	else:
		print('YES')


testcases = int(input())
for testcase in range(testcases):
	(rows, columns) = map(int, input().split())
	counter = 0
	for row in range(rows):
		list1 = list(map(int, input()))[:columns]
		counter += list1.count(1)
	if counter % 2 == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	mat = []
	for i in range(n):
		mat += [i for i in input().split()]
	count = 0
	for i in mat:
		for j in i:
			if j == '1':
				count += 1
	if count % 2 == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for ddfd in range(t):
	(n, m) = map(int, input().split())
	lis = [input() for i in range(n)]
	count = 0
	for i in lis:
		for j in i:
			if j == '1':
				count += 1
	if count % 2 == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	ones = 0
	for i in range(x):
		s = input()
		ones += s.count('1')
	if ones & 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	ans = 0
	for j in range(n):
		s = input()
		x = s.count('1')
		if x % 2 == 1:
			ans += 1
	if ans % 2 == 0:
		print('NO')
	else:
		print('YES')


try:
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		arr = []
		for _ in range(n):
			arr.append(input())
		cnt = 0
		for i in range(n):
			for j in range(m):
				if arr[i][j] == '1':
					cnt += 1
		if cnt % 2 == 0:
			print('NO')
		else:
			print('YES')
except:
	pass


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	lst = list()
	(one, zero) = (0, 0)
	for i in range(n):
		lst.extend(list(map(str, input().split())))
	for i in range(len(lst)):
		for j in range(len(lst[i])):
			if lst[i][j] == '1':
				one += 1
			else:
				zero += 1
	if one % 2 != 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	xor = 0
	arr = []
	for _ in range(n):
		arr.append(input())
	for i in range(n):
		for j in range(m):
			xor = xor ^ int(arr[i][j])
	if xor:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, m) = tuple(map(int, input().split()))
	total_ones = 0
	for i in range(n):
		b = input()
		foo = b.count('1')
		total_ones += foo
	if total_ones % 2:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	ans = 0
	(n, m) = map(int, input().split())
	for j in range(n):
		for i in input():
			if i == '1':
				ans += 1
	if ans % 2 != 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	t -= 1
	(n, m) = [int(x) for x in input().split()]
	a = []
	for i in range(n):
		a.append(input())
	count = 0
	for i in range(n):
		for c in a[i]:
			if c == '1':
				count += 1
	if count % 2 == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	t -= 1
	(n, m) = tuple(map(int, input().split()))
	count = 0
	for i in range(n):
		num = str(input())
		for j in range(m):
			if int(num[j]) == 1:
				count += 1
	if count % 2 == 0:
		print('NO')
	else:
		print('YES')


for q in range(int(input())):
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	li = []
	count = 0
	for i in range(n):
		s = input()
		li2 = [int(i) for i in s]
		count = count + li2.count(1)
	if count % 2 == 0:
		print('NO')
	else:
		print('YES')


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	grid = []
	for j in range(N):
		y = input()
		y = [int(j) for j in str(y)]
		grid += y
	xor = grid[0]
	for k in range(1, len(grid)):
		xor = xor ^ grid[k]
	if xor == 1:
		print('YES')
	else:
		print('NO')


try:
	for _ in range(int(input())):
		(r, c) = map(int, input().split())
		c1 = 0
		for i in range(r):
			l = list(input())
			c1 += l.count('1')
		if c1 == 0:
			print('NO')
		elif c1 % 2 == 0:
			print('NO')
		else:
			print('YES')
except:
	pass


import atexit, sys, os, io, time
from functools import reduce
from itertools import *
from math import *

def solve():
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		s = input()
		l.append(s)
	s = ''
	for j in range(n):
		s += l[j]
	count = 0
	for k in range(len(s)):
		if s[k] == '1':
			count += 1
	if count % 2 == 0:
		print('NO')
	else:
		print('YES')
t = int(input())
for case in range(t):
	solve()


for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	x = 0
	for i in range(a):
		c = list(map(int, input()))
		q = c.count(1)
		x = q + x
	if x % 2 == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(N, M) = map(int, input().split())
	count = 0
	for i in range(N):
		temp = input()
		for x in temp:
			if int(x):
				count += 1
	if count % 2:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	count = 0
	for _ in range(n):
		x = input()
		for i in range(m):
			count ^= int(x[i])
	if count:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	count = 0
	for j in range(n):
		a = input()
		for k in range(m):
			if a[k] == '1':
				count += 1
	if count % 2 != 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	li = []
	for i in range(n):
		s = input()
		if i == 0:
			li.append(s)
		else:
			x = li[-1]
			res = ''
			for j in range(m):
				res += str(int(x[j]) ^ int(s[j]))
			li.append(res)
	ans = 0
	r = li[-1]
	for i in range(m):
		if i == 0:
			ans = int(r[i])
		else:
			ans = ans ^ int(r[i])
	if ans == 1:
		print('YES')
	else:
		print('NO')


def main():
	t = int(input())
	for _ in range(t):
		ones = 0
		(n, m) = map(int, input().split())
		for i in range(n):
			s = input()
			ones += s.count('1')
		if ones % 2 == 1:
			print('YES')
		else:
			print('NO')
import sys, threading
import bisect
import math
import itertools
from sys import stdout
import heapq
from queue import PriorityQueue
sys.setrecursionlimit(2 ** 32 // 2 - 1)
threading.stack_size(1 << 27)
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	matrix = []
	for p in range(n):
		row = input()
		matrix.append(row)
	ans = int(matrix[0][0])
	for p in range(n):
		for s in range(len(matrix[p])):
			if p == 0 and s == 0:
				continue
			ans ^= int(matrix[p][s])
	if ans:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = 0
	for i in range(n):
		for j in input():
			c ^= int(j)
	print(['NO', 'YES'][c])


t = int(input())
while t > 0:
	(m, n) = map(int, input().split())
	flag = 0
	k = []
	for i in range(m):
		l = input()
		k.append(l)
	for i in k:
		for j in i:
			flag ^= int(j)
	if flag == 0:
		print('NO')
	else:
		print('YES')
	t -= 1


from functools import reduce
from operator import xor
print('\n'.join(('YES' if reduce(xor, list((reduce(xor, map(int, input())) for _ in range(int(input().split()[0]))))) else 'NO' for _ in range(int(input())))))


from functools import reduce
from operator import xor
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	total = 0
	for _ in range(N):
		total ^= reduce(xor, map(int, input()))
	if total == 1:
		print('YES')
	else:
		print('NO')


from functools import reduce
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	total = 0
	for _ in range(N):
		total ^= reduce(lambda x, y: x ^ y, map(int, input()))
	if total == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = tuple(map(int, input().split()))
	ans = 0
	for _ in range(n):
		ans += input().count('1')
	if ans % 2 == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t != 0:
	t -= 1
	arr = []
	(n, m) = map(int, input().split())
	for i in range(n):
		new = input()
		arr.append(new)
	c = 0
	for i in arr:
		for j in i:
			c ^= int(j)
	if c == 0:
		print('NO')
	else:
		print('YES')


a = int(input())
for i in range(a):
	b = list(map(int, input().split()))
	count = 0
	for j in range(b[0]):
		s1 = input()
		count += s1.count('1')
	if count % 2 == 1:
		print('YES')
	else:
		print('NO')


import math
for _ in range(int(input())):
	(r, c) = list(map(int, input().split()))
	res = 0
	for i in range(r):
		s = input()
		for g in s:
			if g == '1':
				res += 1
	if res % 2 == 0:
		print('NO')
	else:
		print('YES')


T = int(input())
for i in range(T):
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	S = []
	for i in range(N):
		a = input()
		S.append(list(a))
	ans = 1
	for i in range(len(S)):
		for j in range(len(S[i])):
			ans = ans ^ int(S[i][j])
	if ans == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
while t > 0:
	(N, M) = map(int, input().split())
	grid = []
	count = 0
	for i in range(N):
		s = input()
		for j in s:
			if int(j) == 1:
				count += 1
	if count % 2 == 0:
		print('NO')
	else:
		print('YES')
	t -= 1


t = int(input())
while t > 0:
	t -= 1
	[a, b] = list(map(int, input().rstrip().split()))
	strr = ''
	while a > 0:
		a -= 1
		strr += input()
	countone = strr.count('1')
	if countone % 2 == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	col = []
	for _ in range(n):
		row = input()
		prevBit = 0
		for bit in row:
			prevBit ^= int(bit)
		col.append(prevBit)
	prevBit = 0
	for bit in col:
		prevBit ^= bit
	if prevBit == 1:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(N, M) = map(int, input().split())
	arr = []
	for i in range(N):
		S = list(map(int, list(input())))
		arr.append(S)
	ans = 0
	for i in range(N):
		for j in range(M):
			ans = ans ^ arr[i][j]
	if ans == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	c = 0
	for j in range(m):
		l = [int(x) for x in input()]
		for k in l:
			if k == 1:
				c = c + 1
	if c % 2 == 0:
		print('NO')
	elif c % 2 != 0:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	flag = 0
	for i in range(n):
		for j in input():
			flag ^= int(j)
	if flag:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	count = 0
	(m, n) = map(int, input().split())
	for j in range(0, m):
		d = input()
		count = count + d.count('1')
	if count % 2 == 0:
		print('NO')
	else:
		print('YES')


def solution(arreglo, n, m):
	contador = 0
	for i in range(n):
		for j in range(m):
			if arreglo[i][j] == '1':
				contador += 1
	if contador % 2 == 0:
		print('NO')
	else:
		print('YES')

def main():
	T = int(input())
	for i in range(T):
		(n, m) = map(int, input().split())
		array = []
		for i in range(n):
			string = input()
			array.append(string)
		solution(array, n, m)
main()


ReadStr = lambda : input()
ReadIntList = lambda : list(map(int, input().split()))
ReadStrList = lambda : list(map(str, input().split()))
ReadInt = lambda : int(input())
ReadMultipleValues = lambda : map(int, input().split())
ReadMultipleValuesStr = lambda : map(str, input().split())
for _ in range(ReadInt()):
	(n, m) = ReadMultipleValues()
	n_m = ''
	for i in range(n):
		s = ReadStr()
		n_m += s
	if n_m.count('1') & 1 == 1:
		print('YES')
	else:
		print('NO')


cases = int(input())
for _ in range(cases):
	ones = 0
	zeros = 0
	(c, n) = map(int, input().split())
	for _ in range(c):
		s = input()
		one = s.count('1')
		ones += one
		zeros += n - one
	if ones % 2 != 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	ans = 0
	ar = []
	for i in range(n):
		innerArray = list(' '.join(input()).split())
		ar.append(innerArray)
	ans = 0
	for j in range(n):
		for i in range(m):
			ans ^= int(ar[j][i])
	if ans == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().strip().split(' '))
	cnt = 0
	for i in range(n):
		a = input()
		for i in range(m):
			if a[i] == '1':
				cnt += 1
	if cnt % 2 == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
while t:
	t = t - 1
	(n, m) = map(int, input().split())
	l = []
	c = 0
	for i in range(n):
		s = input()
		for j in s:
			if j == '1':
				c += 1
	if c % 2 == 1:
		print('YES')
	else:
		print('NO')


GI = lambda : int(input())
GIS = lambda : map(int, input().split())
LGIS = lambda : list(GIS())

def main():
	for _ in range(GI()):
		(n, m) = GIS()
		zeros = ones = 0
		for r in range(n):
			for c in input():
				if c == '1':
					ones += 1
		res = 'YES' if ones % 2 else 'NO'
		print(res)
main()


for i in range(int(input())):
	(n, m) = map(int, input().split())
	cnt = 0
	for j in range(n):
		string = input()
		ans = int(string, 2)
		while ans != 0:
			rsb = ans & -ans
			ans -= rsb
			cnt += 1
	if cnt % 2 == 0:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	s = ''
	for i in range(0, n):
		s1 = input()
		s = s + s1
	c = 0
	l1 = list(s)
	for j in l1:
		if int(j) == 1:
			c = c + 1
	if c % 2 != 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(m, n) = list(map(int, input().split()))
	ans = 0
	prr = ['NO', 'YES']
	for j in range(m):
		ans = ans ^ sum(list(map(int, input()))) % 2
	print(prr[ans])


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]

def grid_xor(grd):
	xors = 0
	for i in range(len(grd)):
		for j in range(len(grd[0])):
			xors ^= grd[i][j]
	return xors
for _ in range(RI()):
	(N, M) = RMI()
	grid = [[int(x) for x in input()] for _ in range(N)]
	if grid_xor(grid) == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ones = 0
	for _ in range(n):
		q = input()
		for i in q:
			if i == '1':
				ones += 1
	if ones % 2 == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	A = []
	ans = 0
	for _ in range(n):
		ele = input()
		A.append(ele)
	for i in A:
		for j in i:
			ans ^= int(j)
	if ans == 0:
		print('NO')
	else:
		print('YES')