You are storing an integer array of length m in a database. To maintain internal integrity and protect data, the database stores n copies of this array.

Unfortunately, the recent incident may have altered the stored information in every copy in the database.

It's believed, that the incident altered at most two elements in every copy. You need to recover the original array based on the current state of the database.

In case there are multiple ways to restore the array, report any. If there is no array that differs from every copy in no more than two positions, report that as well.

Input

The first line contains integers n and m (2 ≤ n; 1 ≤ m; n ⋅ m ≤ 250 000) — the number of copies and the size of the array.

Each of the following n lines describes one of the currently stored copies in the database, it consists of m integers s_{i, 1}, s_{i, 2}, ..., s_{i, m} (1 ≤ s_{i, j} ≤ 10^9).

Output

If there is an array consistent with all given copies, print "Yes" and then the array itself. The array must have length m and contain integers between 1 and 10^9 only.

Otherwise, print "No".

If there are multiple possible arrays, print any of them.

Examples

Input


3 4
1 10 10 100
1 1 1 100
10 100 1 100


Output


Yes
1 10 1 100


Input


10 7
1 1 1 1 1 1 1
1 1 1 1 1 1 2
1 1 1 1 1 2 2
1 1 1 1 2 2 1
1 1 1 2 2 1 1
1 1 2 2 1 1 1
1 2 2 1 1 1 1
2 2 1 1 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1 1 1


Output


Yes
1 1 1 1 1 1 1


Input


2 5
2 2 1 1 1
1 1 2 2 2


Output


No

Note

In the first example, the array [1, 10, 1, 100] differs from first and second copies in just one position, and from the third copy in two positions.

In the second example, array [1, 1, 1, 1, 1, 1, 1] is the same as the first copy and differs from all other copies in at most two positions.

In the third example, there is no array differing in at most two positions from every database's copy.

Difficulty: VERY_HARD
Tags: Graph traversal

Constructive algorithms

Implementation

Greedy algorithms

Complete search
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
def solvetestcase():
	(n, m) = [int(e) for e in input().split(' ')]
	db = []
	for _ in range(n):
		db.append([int(e) for e in input().split(' ')])
	return solve_helper(n, m, db)

def solve_helper(n, m, db, start=True):
	found_candidate = -1
	max_diffs = 0
	for i in range(1, n):
		diffs = [j for j in range(m) if db[i][j] != db[0][j]]
		ldiff = len(diffs)
		if ldiff > 4:
			return 'No'
		if ldiff < 3:
			continue
		if ldiff > max_diffs:
			found_candidate = i
			max_diffs = ldiff
	if found_candidate == -1:
		return 'Yes\n' + ' '.join([str(e) for e in db[0]])
	diffs = [j for j in range(m) if db[found_candidate][j] != db[0][j]][:]
	for attempt in range(1, 1 + (1 << len(diffs))):
		current = db[0][:]
		for i in range(len(diffs)):
			if attempt >> i & 1:
				current[diffs[i]] = db[found_candidate][diffs[i]]
		for i in range(n):
			cdiffs = [j for j in range(m) if db[i][j] != current[j]]
			if len(cdiffs) > 2:
				break
		else:
			return 'Yes\n' + ' '.join([str(e) for e in current])
	if start:
		(db[0], db[found_candidate]) = (db[found_candidate], db[0])
		return solve_helper(n, m, db, False)
	return 'No'
print(solvetestcase())


(N, M) = map(int, input().split())
A = []
for i in range(N):
	a = list(map(int, input().split()))
	for j in range(M):
		A.append(a[j])
ans = A[:M]
for i in range(1, N):
	cnt = 0
	lis = []
	for j in range(M):
		if ans[j] != A[i * M + j]:
			lis.append((j, A[i * M + j]))
			cnt += 1
			if cnt > 4:
				print('No')
				exit()
	if cnt > 2:
		break
else:
	print('Yes')
	print(*ans)
	exit()
for (ind, a) in lis:
	ans = A[:M]
	ans[ind] = a
	for i in range(1, N):
		cnt = 0
		lis2 = []
		for j in range(M):
			if ans[j] != A[i * M + j]:
				cnt += 1
				if j != ind:
					lis2.append((j, A[i * M + j]))
			if cnt > 3:
				break
		if cnt > 2:
			break
	else:
		print('Yes')
		print(*ans)
		exit()
	if cnt > 3:
		continue
	for (ind2, a2) in lis2:
		ans = A[:M]
		ans[ind] = a
		ans[ind2] = a2
		for i in range(1, N):
			cnt = 0
			lis2 = []
			for j in range(M):
				if ans[j] != A[i * M + j]:
					cnt += 1
				if cnt > 3:
					break
			if cnt > 2:
				break
		else:
			print('Yes')
			print(*ans)
			exit()
print('No')
exit()


def solve():
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for i in range(n)]
	c = []
	row = 0
	for i in range(1, n):
		c1 = []
		for j in range(m):
			if a[0][j] != a[i][j]:
				c1.append(j)
		if len(c1) > len(c):
			c = c1
			row = i
	if len(c) > 4:
		print('No')
		return
	c = []
	row2 = row
	for i in range(n):
		c1 = []
		for j in range(m):
			if a[row][j] != a[i][j]:
				c1.append(j)
		if len(c1) > len(c):
			c = c1
			row2 = i
	b = a[row2].copy()
	for i in range(2 ** len(c)):
		for j in range(len(c)):
			cc = c[j]
			b[cc] = a[row][cc] if i >> j & 1 != 0 else a[row2][cc]
		bad = False
		for j in range(n):
			cnt = 0
			for k in range(m):
				cnt += int(b[k] != a[j][k])
			if cnt > 2:
				bad = True
				break
		if not bad:
			print('Yes')
			print(' '.join(map(str, b)))
			return
	print('No')
solve()


import io
import os
from collections import Counter, defaultdict, deque
from itertools import product

def solve(N, M, A):

	def getDiff(w1, w2):
		return [i for i in range(M) if w1[i] != w2[i]]

	def fourDiffAnswer(word1, word2, indices):
		assert len(indices) == 4
		w1 = list(word1)
		numIndices = len(indices)
		for mask in range(1 << numIndices):
			for (pos, i) in enumerate(indices):
				if mask >> pos & 1:
					w1[i] = word1[i]
				else:
					w1[i] = word2[i]
			if len(getDiff(w1, word1)) <= 2 and len(getDiff(w1, word2)) <= 2:
				if all((len(getDiff(w1, w2)) <= 2 for w2 in A)):
					return w1
			for i in indices:
				w1[i] = word1
		return False

	def threeDiffAnswer(word1, word2, indices):
		assert len(indices) == 3
		w1 = list(word1)
		numIndices = len(indices)
		for unknownIndex in indices:
			for mask in range(1 << numIndices):
				for (pos, i) in enumerate(indices):
					if mask >> pos & 1:
						w1[i] = word1[i]
					else:
						w1[i] = word2[i]
					if i == unknownIndex:
						w1[i] = -1
				good = True
				cand = set()
				for w2 in A:
					diffs = getDiff(w1, w2)
					if len(diffs) > 3:
						good = False
						break
					if len(diffs) == 3:
						cand.add(w2[unknownIndex])
				if len(cand) > 1:
					good = False
				if good:
					if len(cand) == 1:
						w1[unknownIndex] = next(iter(cand))
					else:
						w1[unknownIndex] = 1
					assert all((len(getDiff(w1, w2)) <= 2 for w2 in A))
					return w1
				for i in indices:
					w1[i] = word1
		return False

	def formatAnswer(ans):
		if not ans:
			return 'No'
		return 'Yes\n' + ' '.join(map(str, ans))
	w1 = A[0]
	mostDiff = (0,)
	for j in range(1, N):
		w2 = A[j]
		indices = getDiff(w1, w2)
		if len(indices) > 4:
			return 'No'
		elif len(indices) == 4:
			return formatAnswer(fourDiffAnswer(w1, w2, indices))
		elif len(indices):
			mostDiff = max(mostDiff, (len(indices), j))
	if mostDiff[0] <= 2:
		return formatAnswer(w1)
	assert mostDiff[0] == 3
	w2 = A[mostDiff[1]]
	return formatAnswer(threeDiffAnswer(w1, w2, getDiff(w1, w2)))
DEBUG = False
if DEBUG:
	import random
	random.seed(10)
	for _ in range(1000000):
		M = random.randint(1, 10)
		orig = [0] * M
		N = random.randint(1, 10)
		A = []
		for i in range(N):
			copy = list(orig)
			i1 = random.randint(0, M - 1)
			i2 = random.randint(0, M - 1)
			copy[i1] = random.randint(0, 10)
			copy[i2] = random.randint(0, 10)
			A.append(copy)
		ans = solve(N, M, A)
		assert not ans.startswith('No')
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(1, TC + 1):
	(N, M) = [int(x) for x in input().split()]
	S = [[int(x) for x in input().split()] for i in range(N)]
	ans = solve(N, M, S)
	print(ans)


import sys

def solve(N, M, A):
	A0 = A[0]
	diff_list = []
	for i in range(1, N):
		diff = 0
		my_list = A[i]
		for j in range(M):
			if my_list[j] != A0[j]:
				diff += 1
		diff_list.append(diff)
	my_max = max(diff_list)
	if my_max < 3:
		print('Yes')
		A0 = [str(x) for x in A0]
		print(' '.join(A0))
		return
	if my_max > 4:
		print('No')
		return
	if my_max >= 3:
		my_max = max(diff_list)
		for i in range(N - 1):
			if diff_list[i] == my_max:
				idx = i + 1
				break
	Ax = A[idx]
	where_diff = []
	for j in range(M):
		if A0[j] != Ax[j]:
			where_diff.append(j)
	new_A = []
	diff_list = [0] + diff_list
	small_diff_list = []
	for i in range(N):
		my_list = []
		small_diff = 0
		for j in where_diff:
			small_diff += A[i][j] != A0[j]
			my_list.append(A[i][j])
		small_diff_list.append(small_diff)
		new_A.append(my_list)
	outside_diff_list = [diff_list[i] - small_diff_list[i] for i in range(N)]
	if my_max == 3:
		for k1 in range(3):
			for k2 in range(3):
				if k1 != k2:
					k3 = 3 - k1 - k2
					keep_from_A0 = where_diff[k1]
					keep_from_Ax = where_diff[k2]
					new_diff_list = []
					for i in range(N):
						new_diff_list.append((A0[keep_from_A0] != A[i][keep_from_A0]) + (Ax[keep_from_Ax] != A[i][keep_from_Ax]))
					merged_diff_list = [new_diff_list[i] + outside_diff_list[i] for i in range(N)]
					if max(merged_diff_list) < 2:
						print('Yes')
						common_seq = [x for x in A0]
						common_seq[keep_from_Ax] = Ax[keep_from_Ax]
						common_seq[where_diff[k3]] = 1
						print(' '.join([str(x) for x in common_seq]))
						return
					elif max(merged_diff_list) == 2:
						lehet_jo = True
						values = -1
						for i in range(N):
							if merged_diff_list[i] == 2:
								if values < 0:
									values = A[i][where_diff[k3]]
								elif values != A[i][where_diff[k3]]:
									lehet_jo = False
						if lehet_jo:
							print('Yes')
							common_seq = [x for x in A0]
							common_seq[keep_from_Ax] = Ax[keep_from_Ax]
							common_seq[where_diff[k3]] = values
							print(' '.join([str(x) for x in common_seq]))
							return
	if my_max == 4:
		idx_tuples = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
		for idx_tuple in idx_tuples:
			vals = [A0[where_diff[i]] if i in idx_tuple else Ax[where_diff[i]] for i in range(4)]
			new_diff_list = []
			for i in range(N):
				diff = 0
				for j in range(4):
					if new_A[i][j] != vals[j]:
						diff += 1
				new_diff_list.append(diff)
			merged_diff_list = [new_diff_list[i] + outside_diff_list[i] for i in range(N)]
			if max(merged_diff_list) <= 2:
				print('Yes')
				common_seq = [x for x in A0]
				for ii in range(4):
					common_seq[where_diff[ii]] = vals[ii]
				print(' '.join([str(x) for x in common_seq]))
				return
	print('No')
	return

def run():
	out = ''
	(N, M) = [int(x) for x in input().split()]
	A_list = []
	for i in range(N):
		A = [int(x) for x in input().split()]
		A_list.append(A)
	solve(N, M, A_list)
run()


from collections import deque
from typing import List, Optional

class ContestParser:

	def __init__(self):
		self.buffer = deque()

	def next_token(self) -> str:
		if len(self.buffer) == 0:
			self.buffer.extend(input().split())
		return self.buffer.popleft()

	def next_int(self) -> int:
		return int(self.next_token())

	def get_int_list(self, n: int) -> List[int]:
		return [self.next_int() for i in range(n)]

def find_diffs(a1: List[int], a2: List[int]) -> List[int]:
	return [i for (i, (e1, e2)) in enumerate(zip(a1, a2)) if e1 != e2]

def attempt(arrays: List[List[int]], guess: List[int], changes_left: int, max_changes: int) -> Optional[List[int]]:
	for array in arrays:
		diffs = find_diffs(guess, array)
		if len(diffs) <= max_changes:
			continue
		if len(diffs) > max_changes + changes_left:
			return None
		for d in diffs:
			new_guess = guess.copy()
			new_guess[d] = array[d]
			result = attempt(arrays, new_guess, changes_left - 1, max_changes)
			if result is not None:
				return result
		return None
	return guess
parser = ContestParser()
n = parser.next_int()
m = parser.next_int()
arrays = [parser.get_int_list(m) for i in range(n)]
result = attempt(arrays, arrays[0], 2, 2)
if result is not None:
	print('Yes')
	print(' '.join((str(x) for x in result)))
else:
	print('No')


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

def cmp(i, j):
	ans = 0
	for k in range(m):
		if a[i][k] != a[j][k]:
			ans += 1
	return ans

def dif(i, j):
	res = []
	for k in range(m):
		if a[i][k] != a[j][k]:
			res.append(k)
	return res
t = 1
for i in range(t):
	(n, m) = RL()
	a = []
	for i in range(n):
		a.append(RLL())
	thr = four = -1
	for i in range(1, n):
		cur = cmp(0, i)
		if cur > 4:
			print('No')
			exit()
		if cur == 4:
			four = i
		elif cur == 3:
			thr = i
	if thr == four == -1:
		print('Yes')
		print(*a[0])
	else:
		if four != -1:
			res = dif(0, four)
			for (x, y) in combinations(res, 2):
				(b, c) = (a[0][x], a[0][y])
				(a[0][x], a[0][y]) = (a[four][x], a[four][y])
				f = True
				for i in range(1, n):
					if cmp(0, i) > 2:
						f = False
						break
				if f:
					print('Yes')
					print(*a[0])
					exit()
				(a[0][x], a[0][y]) = (b, c)
		else:
			res = dif(0, thr)
			for (x, y) in permutations(res, 2):
				(b, c) = (a[0][x], a[0][y])
				(a[0][x], a[0][y]) = (a[thr][x], 0)
				f = True
				for i in range(1, n):
					cur = cmp(0, i)
					if cur > 3:
						f = False
						break
					if cur == 3:
						if a[0][y] == 0:
							a[0][y] = a[i][y]
						else:
							f = False
							break
				if f:
					if a[0][y] == 0:
						a[0][y] = c
					print('Yes')
					print(*a[0])
					exit()
				(a[0][x], a[0][y]) = (b, c)
		print('No')