You are given a binary matrix $a$ of size $n \times m$. A binary matrix is a matrix where each element is either $0$ or $1$.

You may perform some (possibly zero) operations with this matrix. During each operation you can inverse the row of this matrix or a column of this matrix. Formally, inverting a row is changing all values in this row to the opposite ($0$ to $1$, $1$ to $0$). Inverting a column is changing all values in this column to the opposite.

Your task is to sort the initial matrix by some sequence of such operations. The matrix is considered sorted if the array $[a_{1, 1}, a_{1, 2}, \dots, a_{1, m}, a_{2, 1}, a_{2, 2}, \dots, a_{2, m}, \dots, a_{n, m - 1}, a_{n, m}]$ is sorted in non-descending order.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 200$) — the number of rows and the number of columns in the matrix.

The next $n$ lines contain $m$ integers each. The $j$-th element in the $i$-th line is $a_{i, j}$ ($0 \le a_{i, j} \le 1$) — the element of $a$ at position $(i, j)$.


-----Output-----

If it is impossible to obtain a sorted matrix, print "NO" in the first line.

Otherwise print "YES" in the first line. In the second line print a string $r$ of length $n$. The $i$-th character $r_i$ of this string should be '1' if the $i$-th row of the matrix is inverted and '0' otherwise. In the third line print a string $c$ of length $m$. The $j$-th character $c_j$ of this string should be '1' if the $j$-th column of the matrix is inverted and '0' otherwise. If there are multiple answers, you can print any.


-----Examples-----
Input
2 2
1 1
0 1

Output
YES
00
10

Input
3 4
0 0 0 1
0 0 0 0
1 1 1 1

Output
YES
010
0000

Input
3 3
0 0 0
1 0 1
1 1 0

Output
NO

Source: codeforces | Difficulty: HARD
Tags: Complete search

Constructive algorithms


Solutions:
import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(n)]
for i in range(m):
	ANSR = [0] * n
	ANSC = [0] * m
	for j in range(i):
		if A[0][j] == 1:
			ANSC[j] = 1
	for j in range(i, m):
		if A[0][j] == 0:
			ANSC[j] = 1
	for r in range(1, n):
		B = set()
		for c in range(m):
			if ANSC[c] == 0:
				B.add(A[r][c])
			else:
				B.add(1 - A[r][c])
		if len(B) >= 2:
			break
		if max(B) == 0:
			ANSR[r] = 1
	else:
		print('YES')
		print(''.join(map(str, ANSR)))
		print(''.join(map(str, ANSC)))
		return
ANSR = [0] * n
ANSC = [0] * m
for j in range(m):
	if A[0][j] == 1:
		ANSC[j] = 1
flag = 0
for r in range(1, n):
	if flag == 0:
		B = []
		for c in range(m):
			if ANSC[c] == 0:
				B.append(A[r][c])
			else:
				B.append(1 - A[r][c])
		if max(B) == 0:
			continue
		elif min(B) == 1:
			ANSR[r] = 1
			continue
		else:
			OI = B.index(1)
			if min(B[OI:]) == 1:
				flag = 1
				continue
			OO = B.index(0)
			if max(B[OO:]) == 0:
				flag = 1
				ANSR[r] = 1
				continue
			else:
				print('NO')
				return
	else:
		B = set()
		for c in range(m):
			if ANSC[c] == 0:
				B.add(A[r][c])
			else:
				B.add(1 - A[r][c])
		if len(B) >= 2:
			break
		if max(B) == 0:
			ANSR[r] = 1
else:
	print('YES')
	print(''.join(map(str, ANSR)))
	print(''.join(map(str, ANSC)))
	return
print('NO')


def inverse_row(row):
	inv_row[row] = not inv_row[row]
	for i in range(m):
		a[row][i] = not a[row][i]

def inverse_col(col):
	inv_col[col] = not inv_col[col]
	for i in range(n):
		a[i][col] = not a[i][col]

def check_row(row):
	if a[row][0] < a[row - 1][m - 1]:
		return False
	for i in range(1, m):
		if a[row][i] < a[row][i - 1]:
			return False
	return True

def check_all():
	for i in range(1, n):
		if a[i][0]:
			inverse_row(i)
		if check_row(i):
			continue
		inverse_row(i)
		if check_row(i):
			continue
		return False
	return True

def print_result():
	print('YES')
	for i in inv_row:
		print(int(i), end='')
	print('')
	for i in inv_col:
		print(int(i), end='')
	print('')
(n, m) = [int(i) for i in input().split(' ')]
a = []
inv_row = [False] * n
inv_col = [False] * m
had_result = False
for i in range(n):
	a.append([bool(int(i)) for i in input().split(' ')])
for i in range(m):
	if a[0][i]:
		inverse_col(i)
if check_all():
	print_result()
	had_result = True
if not had_result:
	for i in range(m - 1, -1, -1):
		inverse_col(i)
		if check_all():
			print_result()
			had_result = True
			break
if not had_result:
	print('NO')


import sys
sys.setrecursionlimit(2000)
from collections import Counter
from functools import reduce

def get_info(row):
	s = set(row)
	if len(s) == 1:
		homogeneous = True
	else:
		homogeneous = False
	is_sorted = True
	for (ind, val) in enumerate(row[1:]):
		if val < row[ind]:
			is_sorted = False
	is_reverse_sorted = True
	for ind in range(n - 1, 1, -1):
		if row[ind - 1] > row[ind]:
			is_reversed_sorted = False
	return (homogeneous, is_sorted, 0 in s, 1 in s, is_reverse_sorted)

def mc(A, col):
	for row in A:
		row[col] = 1 - row[col]

def mr(A, row):
	for (ind, val) in enumerate(A[row]):
		A[row][ind] = 1 - A[row][ind]

def is_pos(A, flip, start_row, end_row, rows, cols):
	pos = True
	for row in range(start_row, end_row + 1):
		info = get_info(A[row])
		if info[0]:
			must_b = '0' if not flip else '1'
			if must_b == '0':
				if info[2]:
					pass
				else:
					mr(A, row)
					rows[row] = '1'
			elif info[3]:
				pass
			else:
				mr(A, row)
				rows[row] = '1'
		elif flip:
			pos = False
			break
		elif info[1]:
			flip = True
		elif info[4]:
			mr(A, row)
			rows[row] = '1'
			flip = True
		else:
			pos = False
			break
	return pos

def force_row_to_val(A, row, val, rows, cols):
	info = get_info(A[row])
	check_ind = 2 if val == 1 else 3
	if info[0]:
		if info[check_ind]:
			mr(A, row)
			rows[row] = '1'
		else:
			pass
	else:
		for i in range(m):
			if A[row][i] != val:
				mc(A, i)
				cols[i] = '1'
(n, m) = [int(val) for val in sys.stdin.readline().split()]
A = [[int(val) for val in sys.stdin.readline().split()] for row in range(n)]
rows1 = ['0'] * n
cols1 = ['0'] * m
rows2 = ['0'] * n
cols2 = ['0'] * m
from copy import deepcopy
A1 = deepcopy(A)
A2 = deepcopy(A)
force_row_to_val(A1, -1, 1, rows1, cols1)
pos1 = is_pos(A1, False, 0, n - 2, rows1, cols1)
force_row_to_val(A2, 0, 0, rows2, cols2)
pos2 = is_pos(A2, False, 1, n - 1, rows2, cols2)
if pos1:
	cols = cols1
	rows = rows1
elif pos2:
	cols = cols2
	rows = rows2
if pos1 or pos2:
	print('YES')
	for val in rows:
		print(val, end='')
	print('')
	for val in cols:
		print(val, end='')
	print('')
else:
	print('NO')


import io
import os
from collections import defaultdict
from sys import stdin, stdout

def main():
	(n, m) = map(int, input().split())
	g = [[] for _ in range(n)]
	for r in range(n):
		g[r] = list(map(int, input().split()))
	cols = [0 for _ in range(m)]
	rows = [0 for _ in range(n)]

	def prefZeros(vec):
		f = False
		for val in vec:
			if val == 1:
				if not f:
					f = True
			elif f:
				return False
		return True

	def prefOnes(vec):
		f = False
		for val in vec:
			if val == 0:
				if not f:
					f = True
			elif f:
				return False
		return True

	def case1():
		for i in range(m):
			cols[i] = 0
		for i in range(n):
			rows[i] = 0
		for i in range(m):
			if g[0][i] == 1:
				cols[i] = 1
		flip = False
		for r in range(1, n):
			row = [g[r][c] ^ cols[c] for c in range(m)]
			s = sum(row)
			is_pref_zeros = prefZeros(row)
			is_pref_ones = prefOnes(row)
			if s == 0:
				if flip:
					rows[r] = 1
			elif s == m:
				if not flip:
					rows[r] = 1
			elif is_pref_zeros:
				if not flip:
					flip = True
				else:
					rows[r] = 1
			elif is_pref_ones:
				rows[r] = 1
				if not flip:
					flip = True
				else:
					return False
			else:
				return False
		return True

	def case2():
		for i in range(m):
			cols[i] = 0
		for i in range(n):
			rows[i] = 0
		for i in range(m):
			if g[n - 1][i] == 0:
				cols[i] = 1
		flip = False
		for r in range(n - 1):
			row = [g[r][c] ^ cols[c] for c in range(m)]
			s = sum(row)
			is_pref_zeros = prefZeros(row)
			is_pref_ones = prefOnes(row)
			if s == 0:
				if flip:
					rows[r] = 1
			elif s == m:
				if not flip:
					rows[r] = 1
			elif is_pref_zeros:
				if not flip:
					flip = True
				else:
					rows[r] = 1
			elif is_pref_ones:
				rows[r] = 1
				if not flip:
					flip = True
				else:
					return False
			else:
				return False
		return True
	if case1() or case2():
		print('YES')
		print(''.join((str(r) for r in rows)))
		print(''.join((str(c) for c in cols)))
	else:
		print('NO')
main()


rint = lambda : int(input())
rmint = lambda : map(int, input().split())
rlist = lambda : list(rmint())
(n, m) = rmint()
a = []
for i in range(n):
	a.append(rlist())
ax = []
for i in range(n):
	ax.append(0)
ay = []
for i in range(m):
	ay.append(0)

def inv(x, y):
	a[x][y] = 1 - a[x][y]

def invx(x):
	for y in range(m):
		inv(x, y)
	ax[x] = 1 - ax[x]

def invy(y):
	for x in range(n):
		inv(x, y)
	ay[y] = 1 - ay[y]

def ex():
	print('YES')
	for i in ax:
		print(i, end='')
	print()
	for i in ay:
		print(i, end='')
	exit(0)
if n == 1:
	ay = a[0]
	ex()

def D(x, v):
	for y in range(m):
		if a[x][y] != v:
			invy(y)
	fx = -1
	fy = -1
	for i in range(n):
		for j in range(m - 1):
			if a[i][j] != a[i][j + 1]:
				fx = i
				fy = j
	if fx < 0:
		for i in range(n):
			if a[i][0]:
				invx(i)
	else:
		if a[fx][fy] > a[fx][fy + 1]:
			invx(fx)
		for i in range(fx):
			if a[i][0]:
				invx(i)
		for i in range(fx + 1, n):
			if not a[i][0]:
				invx(i)
	srt = 1
	for i in range(n):
		for j in range(m):
			if i + 1 == n and j + 1 == m:
				break
			t = i * m + j + 1
			x = t // m
			y = t % m
			if a[x][y] < a[i][j]:
				srt = 0
	if srt:
		ex()
D(0, 0)
D(n - 1, 1)
print('NO')


import sys
n = 0
m = 0
sq = [[0] * 310] * 310
ansx = []
ansy = []
tmp = [[0] * 310] * 310

def chk():
	val = []
	for i in range(0, n):
		for j in range(0, m):
			val.append(tmp[i][j])
	Len = len(val)
	for i in range(1, Len):
		if val[i - 1] > val[i]:
			return False
	return True
(n, m) = map(int, input().split())
for i in range(0, n):
	sq[i] = list(map(int, input().split()))
for i in range(0, n):
	tmp[i] = list(sq[i])
for i in range(0, m):
	if tmp[0][i] == 1:
		ansy.append(1)
		for j in range(0, n):
			tmp[j][i] = 1 - tmp[j][i]
	else:
		ansy.append(0)
op = 0
for i in range(0, n):
	flag0 = 0
	flag1 = 0
	for j in range(0, m):
		if tmp[i][j] == 0:
			flag0 = 1
		else:
			flag1 = 1
	if flag0 == 1 and flag1 == 1:
		op = 1
		if tmp[i][0] == 1:
			ansx.append(1)
			for j in range(0, m):
				tmp[i][j] = 1 - tmp[i][j]
		else:
			ansx.append(0)
	elif flag0 == 1:
		if op == 0:
			ansx.append(0)
		elif op == 1:
			ansx.append(1)
			for j in range(0, m):
				tmp[i][j] = 1 - tmp[i][j]
	elif flag1 == 1:
		if op == 0:
			ansx.append(1)
			for j in range(0, m):
				tmp[i][j] = 1 - tmp[i][j]
		else:
			ansx.append(0)
if chk():
	print('YES')
	for i in range(0, n):
		print(ansx[i], end='')
	print()
	for i in range(0, m):
		print(ansy[i], end='')
	sys.exit()
for i in range(0, n):
	tmp[i] = list(sq[i])
ansx = []
ansy = []
for i in range(0, m):
	if tmp[n - 1][i] == 1:
		ansy.append(0)
	else:
		ansy.append(1)
		for j in range(0, n):
			tmp[j][i] = 1 - tmp[j][i]
op = 0
for i in range(0, n):
	flag0 = 0
	flag1 = 0
	for j in range(0, m):
		if tmp[i][j] == 1:
			flag1 = 1
		else:
			flag0 = 1
	if flag1 == 1 and flag0 == 1:
		op = 1
		if tmp[i][0] == 1:
			ansx.append(1)
			for j in range(0, m):
				tmp[i][j] = 1 - tmp[i][j]
		else:
			ansx.append(0)
	elif flag0 == 1:
		if op == 0:
			ansx.append(0)
		else:
			ansx.append(1)
			for j in range(0, m):
				tmp[i][j] = 1 - tmp[i][j]
	elif flag1 == 1:
		if op == 1:
			ansx.append(0)
		else:
			ansx.append(1)
			for j in range(0, m):
				tmp[i][j] = 1 - tmp[i][j]
if chk():
	print('YES')
	for i in range(0, n):
		print(ansx[i], end='')
	print()
	for i in range(0, m):
		print(ansy[i], end='')
	sys.exit()
print('NO')


def check(a):
	n = len(a)
	m = len(a[0])
	if a[0][-1] == 1:
		flag = True
	else:
		flag = False
	ones = [1] * m
	zeros = [0] * m
	r = [0] * n
	c = [0] * m
	for i in range(1, n):
		if flag:
			if a[i] == ones:
				continue
			elif a[i] == zeros:
				r[i] ^= 1
			else:
				return (None, None)
		elif a[i] == ones:
			r[i] ^= 1
		elif a[i] == zeros:
			continue
		elif a[i] == sorted(a[i]):
			flag = True
		elif a[i] == sorted(a[i], reverse=True):
			flag = True
			r[i] ^= 1
		else:
			return (None, None)
	return (r, c)

def combine(a, b):
	return list(map(lambda x: x[0] ^ x[1], zip(a, b)))

def solve():
	(n, m) = map(int, input().split())
	a = [[0] * m for _ in range(n)]
	for i in range(n):
		a[i] = list(map(int, input().split()))
	for t in range(2):
		for r in range(m):
			acur = [[a[i][j] for j in range(m)] for i in range(n)]
			c1 = [0] * m
			for i in range(m):
				acur[0][i] ^= t
				if acur[0][i] == 1 and i <= r:
					c1[i] ^= 1
					for j in range(n):
						acur[j][i] ^= 1
				elif acur[0][i] == 0 and i > r:
					c1[i] ^= 1
					for j in range(n):
						acur[j][i] ^= 1
			(r, c) = check(acur)
			if r:
				print('YES')
				r[0] ^= t
				print(*r, sep='')
				print(*combine(c, c1), sep='')
				return
	print('NO')
for _ in range(1):
	solve()