Hongcow likes solving puzzles.

One day, Hongcow finds two identical puzzle pieces, with the instructions "make a rectangle" next to them. The pieces can be described by an n by m grid of characters, where the character 'X' denotes a part of the puzzle and '.' denotes an empty part of the grid. It is guaranteed that the puzzle pieces are one 4-connected piece. See the input format and samples for the exact details on how a jigsaw piece will be specified.

The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces also cannot overlap.

You are given as input the description of one of the pieces. Determine if it is possible to make a rectangle from two identical copies of the given input. The rectangle should be solid, i.e. there should be no empty holes inside it or on its border. Keep in mind that Hongcow is not allowed to flip or rotate pieces and they cannot overlap, i.e. no two 'X' from different pieces can share the same position.


-----Input-----

The first line of input will contain two integers n and m (1 ≤ n, m ≤ 500), the dimensions of the puzzle piece.

The next n lines will describe the jigsaw piece. Each line will have length m and will consist of characters '.' and 'X' only. 'X' corresponds to a part of the puzzle piece, '.' is an empty space.

It is guaranteed there is at least one 'X' character in the input and that the 'X' characters form a 4-connected region.


-----Output-----

Output "YES" if it is possible for Hongcow to make a rectangle. Output "NO" otherwise.


-----Examples-----
Input
2 3
XXX
XXX

Output
YES

Input
2 2
.X
XX

Output
NO

Input
5 5
.....
..X..
.....
.....
.....

Output
YES



-----Note-----

For the first sample, one example of a rectangle we can form is as follows 

111222

111222



For the second sample, it is impossible to put two of those pieces without rotating or flipping to form a rectangle.

In the third sample, we can shift the first tile by one to the right, and then compose the following rectangle: 

.....

..XX.

.....

.....

.....

Difficulty: MEDIUM
Tags: Implementation

Starter code:

Solutions:
import sys
(n, m) = map(int, input().split())
gg = [input() for i in range(n)]
used = 0
fir = [-1, -1]
sec = [-1, -1]
for i in range(n):
	for j in range(m):
		if gg[i][j] == 'X':
			if not used:
				used = 1
				fir = [i, j]
			sec = [i, j]
for i in range(fir[0], sec[0] + 1):
	for j in range(fir[1], sec[1] + 1):
		if gg[i][j] == '.':
			print('NO')
			sys.exit(0)
for i in range(n):
	for j in range(m):
		if fir[0] <= i <= sec[0] and fir[1] <= j <= sec[1]:
			continue
		if gg[i][j] == 'X':
			print('NO')
			sys.exit(0)
print('YES')


[n, m] = list(map(int, input().split()))
p = []
for i in range(n):
	p.append(input())
minx = 1000
miny = 1000
maxx = 0
maxy = 0
for i in range(n):
	for j in range(m):
		if p[i][j] == 'X':
			miny = min(miny, i)
			maxy = max(maxy, i)
			minx = min(minx, j)
			maxx = max(maxx, j)
for i in range(miny, maxy + 1):
	for j in range(minx, maxx + 1):
		if p[i][j] != 'X':
			print('NO')
			exit(0)
print('YES')


def main():
	import re
	(n, m) = list(map(int, input().split()))
	left = right = -1
	for i in range(n):
		mt = re.search('X+', input())
		if mt is not None:
			t = mt.start()
			if t != left != -1:
				print('NO')
				break
			left = t
			t = mt.end()
			if t != right != -1:
				print('NO')
				break
			right = t
	else:
		print('YES')
main()


(n, m) = map(int, input().split())
v = []
for i in range(n):
	line = input()
	v.append(line)
u = n
d = 0
l = m
r = 0
for i in range(n):
	for j in range(m):
		if v[i][j] == 'X':
			if i < u:
				u = i
			if i > d:
				d = i
			if j < l:
				l = j
			if j > r:
				r = j
for i in range(u, d + 1):
	for j in range(l, r + 1):
		if v[i][j] == '.':
			print('NO')
			exit()
print('YES')


import sys
(n, m) = map(int, input().split())
cnt = 0
r = c = 500
r1 = c1 = 0
for i in range(n):
	s = input()
	for j in range(m):
		if s[j] == 'X':
			cnt += 1
			if i < r:
				r = i
			if i > r1:
				r1 = i
			if j < c:
				c = j
			if j > c1:
				c1 = j
if (r1 - r + 1) * (c1 - c + 1) == cnt:
	print('YES')
else:
	print('NO')


(n, m) = list(map(int, input().split()))
empthy = '.' * m
last = ''
mistake = False
for i in range(n):
	s = input()
	if s != empthy:
		if last == '':
			last = s
		elif last != s:
			mistake = True
			break
if mistake:
	print('NO')
else:
	print('YES')


from sys import stdin, stdout

def ri():
	return map(int, input().split())
(n, m) = ri()
found = 0
for i in range(n):
	r = input()
	if found == 0 and 'X' in r:
		r0 = r
		found = 1
		continue
	if found and 'X' in r:
		if r != r0:
			print('NO')
			exit()
print('YES')


def f():
	(n, m) = map(int, input().split())
	p = [input() for _ in range(n)]
	c = 0
	t = 0
	for i in range(n):
		for j in range(m):
			if p[i][j] == 'X':
				c += 1
				xc = 0
				if t > 0:
					continue
				t = 0
				for k in range(j, m):
					if p[i][k] != 'X':
						break
					xc += 1
					t += 1
				for y in range(i + 1, n):
					if p[y][j] != 'X':
						break
					xtc = 0
					for k in range(j, m):
						if p[y][k] != 'X':
							break
						xtc += 1
						t += 1
					if xc != xtc:
						return False
	return c == t
print('YES' if f() else 'NO')


(n, m) = map(int, input().split())
s = set((input() for i in range(n)))
s.discard('.' * m)
print('YES' if len(s) == 1 else 'NO')


def f():
	s = input().split()
	m = int(s[0])
	n = int(s[1])
	ss = []
	for i in range(m):
		ss.append(input())
	for i in range(m):
		for j in range(n):
			if ss[i][j] == 'X':
				return (ss, m, n, i, j)

def ff(ss, m, n):
	for k in range(m - 1, -1, -1):
		for l in range(n - 1, -1, -1):
			if ss[k][l] == 'X':
				return (k, l)
(ss, m, n, i, j) = f()
(k, l) = ff(ss, m, n)
sss = []
for x in range(m):
	s = ''
	for y in range(n):
		if i <= x and x <= k and (j <= y) and (y <= l):
			s += 'X'
		else:
			s += '.'
	sss.append(s)
if ss == sss:
	print('YES')
else:
	print('NO')


(H, W) = map(int, input().split())
p = []
for i in range(H):
	p.append(list(input()))
l = u = +100500
b = r = -100500
for i in range(H):
	for j in range(W):
		if p[i][j] == 'X':
			l = min(l, j)
			r = max(r, j)
			u = min(u, i)
			b = max(b, i)
for i in range(u, b + 1):
	for j in range(l, r + 1):
		if p[i][j] == '.':
			print('NO')
			return
print('YES')


(m, n) = [int(i) for i in input().split()]
started = False
failed = False
finished = False
t = [-5, -5]
blank = '.' * n
for i in range(m):
	s = input()
	if 'X' in s:
		if finished:
			failed = True
			break
		if not started:
			started = True
			first = False
			second = False
			for j in range(len(s)):
				if first:
					if s[j] != 'X':
						second = True
						t[1] = j
						break
				elif s[j] == 'X':
					first = True
					t[0] = j
			if not second:
				t[1] = len(s)
		if s != '.' * t[0] + 'X' * (t[1] - t[0]) + '.' * (n - t[1]):
			failed = True
			break
	elif started:
		finished = True
if failed:
	print('NO')
else:
	print('YES')


(n, m) = map(int, input().strip().split())
N = [0] * n
M = [0] * m
for i in range(n):
	a = input().strip()
	for j in range(m):
		if a[j] == 'X':
			N[i] = N[i] + 1
			M[j] = M[j] + 1
c = 0
flag = 1
for i in N:
	if i != 0 and c == 0:
		c = i
	if i != 0 and i != c:
		flag = 0
		break
c = 0
for i in M:
	if i != 0 and c == 0:
		c = i
	if i != 0 and i != c:
		flag = 0
		break
if flag == 1:
	print('YES')
else:
	print('NO')


ds = [int(v) for v in input().split(' ')]
vs = []
c = 'X'
(l, r) = (None, None)
(t, b) = (None, None)
for y in range(ds[0]):
	vs += [input()]
	if c in vs[y]:
		t = y if t is None else t
		b = y
		(cl, cr) = (vs[y].find(c), vs[y].rfind(c))
		l = min(l or cl, cl)
		r = max(r or cr, cr)
for y in range(ds[0]):
	for x in range(ds[1]):
		if l <= x <= r and t <= y <= b:
			if vs[y][x] != c:
				print('NO')
				exit()
		elif vs[y][x] == c:
			print('NO')
			exit()
print('YES')


def main():
	(n, m) = list(map(int, input().split()))
	left = None
	right = None
	for _ in range(n):
		line = input().strip()
		cur_l = line.find('X')
		if cur_l != -1:
			if left is None:
				left = cur_l
			elif left != cur_l:
				print('NO')
				return
			cur_r = line.rfind('X')
			if right is None:
				right = cur_r
			elif right != cur_r:
				print('NO')
				return
			if '.' in line[cur_l:cur_r]:
				print('NO')
				return
	print('YES')

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
(cnt, l, r, u, d) = (0, n, 0, m, 0)
for i in range(n):
	s = input()
	for j in range(m):
		if s[j] == 'X':
			cnt += 1
			l = min(l, i)
			u = min(u, j)
			r = max(r, i)
			d = max(d, j)
print('YES' if cnt == (r - l + 1) * (d - u + 1) else 'NO')


(n, m) = list(map(int, input().split()))
a = []
for i in range(n):
	a.append(input())
inf = 10 ** 9
(p, q) = (inf, inf)
(r, s) = (-1, -1)
for i in range(n):
	for j in range(m):
		if a[i][j] == 'X':
			p = min(p, i)
			q = min(q, j)
			r = max(r, i)
			s = max(s, j)
ok = True
for i in range(n):
	for j in range(m):
		if a[i][j] == 'X':
			ok &= p <= i <= r and q <= j <= s
		if a[i][j] == '.':
			ok &= not (p <= i <= r and q <= j <= s)
if ok:
	print('YES')
if not ok:
	print('NO')


import sys
(n, m) = map(int, input().split())
i = 0
t = []
for i in range(n):
	t.append('')
	t[i] = input()
j = 0
for i in range(n):
	t[i] = '.' + t[i] + '.'
ppc = ''
ppc = '.' * (m + 2)
t.insert(0, ppc)
t.append(ppc)
d = 0
sch = 0
b = 0
tr = True
for i in range(n + 2):
	for j in range(m + 2):
		if t[i][j] == 'X':
			d = j
			while d < m and t[i][d] == 'X':
				d += 1
			b = i
			while t[b][j:d + 1] == t[i][j:d + 1]:
				if t[b][j - 1] != 'X' and t[b][d + 1] != 'X':
					b += 1
				else:
					print('NO')
					sys.exit()
			if 'X' in t[b][j:d + 1]:
				print('NO')
				sys.exit()
			else:
				print('YES')
				sys.exit()


(n, m) = map(int, input().split())
mat = [''] * n
for i in range(n):
	mat[i] = input()
(mnx, mny) = (n + 1, m + 1)
(mxx, mxy) = (0, 0)
cnt = 0
for i in range(n):
	for j in range(m):
		if mat[i][j] == 'X':
			mnx = min(mnx, i)
			mxx = max(mxx, i)
			mny = min(mny, j)
			mxy = max(mxy, j)
			cnt += 1
if cnt == 0:
	print('NO')
else:
	ans = (mxx - mnx + 1) * (mxy - mny + 1) == cnt
	print('YES' if ans else 'NO')


def Main():
	(n, m) = map(int, input().split())
	dp = [input().rstrip() for i in range(n)]
	(mxX, mnX, mxY, mnY) = (-1, n, -1, m)
	cnt = 0
	for i in range(n):
		for j in range(m):
			if dp[i][j] == 'X':
				mxX = max(mxX, i)
				mnX = min(mnX, i)
				mxY = max(mxY, j)
				mnY = min(mnY, j)
				cnt += 1
	if (mxX - mnX + 1) * (mxY - mnY + 1) == cnt:
		print('YES')
	else:
		print('NO')
Main()


(h, w) = map(int, input().split())
g = [input() for _ in range(h)]
mh = mw = 10000000
Mh = Mw = 0
for i in range(h):
	for j in range(w):
		if g[i][j] == 'X':
			mh = min(mh, i)
			Mh = max(Mh, i)
			mw = min(mw, j)
			Mw = max(Mw, j)
r = 'YES'
for i in range(h):
	for j in range(w):
		if (g[i][j] == 'X') != (mh <= i <= Mh and mw <= j <= Mw):
			r = 'NO'
print(r)


(n, m) = map(int, input().split())
dic = {}
for i in range(n):
	dic[i] = input()
first = False
for i in range(n):
	for j in range(m):
		if dic[i][j] == 'X':
			corner1 = (i, j)
			first = True
			break
	if first:
		break
for i in range(corner1[0], n + 1):
	if i == n or dic[i][corner1[1]] == '.':
		corner2 = i - 1
		break
for i in range(corner1[1], m + 1):
	if i == m or dic[corner1[0]][i] == '.':
		corner3 = i - 1
		break
rec = True
for i in range(n):
	for j in range(m):
		if i < corner1[0] or i > corner2 or j < corner1[1] or (j > corner3):
			if dic[i][j] == 'X':
				rec = False
				break
		elif dic[i][j] == '.':
			rec = False
			break
if rec:
	print('YES')
else:
	print('NO')


x = input().split()
n = []
for i in range(int(x[0])):
	n.append(input())
import sys
for i in range(len(n)):
	for j in range(len(n[i])):
		if n[i][j] == 'X':
			q_stop = i
			break
for i in range(len(n) - 1, -1, -1):
	for j in range(len(n[i])):
		if n[i][j] == 'X':
			q_start = i
			break
a = n[q_start]
for i in range(q_start + 1, q_stop + 1):
	if n[i] == a:
		continue
	else:
		print('NO')
		sys.exit()
print('YES')


def codeforces(piece):
	row_number = 0
	for row in piece:
		num = row.count('X')
		if num == 0:
			continue
		if row_number == 0:
			row_number = num
			continue
		if num != row_number:
			return 'NO'
	col_number = 0
	cols = [[row[i] for row in piece] for i in range(len(piece[0]))]
	for col in cols:
		num = col.count('X')
		if num == 0:
			continue
		if col_number == 0:
			col_number = num
			continue
		if num != col_number:
			return 'NO'
	return 'YES'
(rows, _) = input().split()
rows = int(rows)
piece = []
for _ in range(rows):
	line = input()
	piece.append(line)
print(codeforces(piece))


(n, m) = map(int, input().split())
flag = False
s1 = ''
for i in range(n):
	s = input()
	if s.find('X') > -1:
		if s1 == '':
			s1 = s
			flag = True
		elif s1 == s:
			flag = True
		else:
			flag = False
			break
if flag:
	print('YES')
else:
	print('NO')


import sys
(n, m) = map(int, input().split())
a = [input() for _ in range(n)]
(min_i, min_j) = (n, m)
(max_i, max_j) = (0, 0)
for i in range(n):
	for j in range(m):
		if a[i][j] == 'X':
			(min_i, min_j) = (min(min_i, i), min(min_j, j))
			(max_i, max_j) = (max(max_i, i), max(max_j, j))
for i in range(min_i, max_i + 1):
	for j in range(min_j, max_j + 1):
		if a[i][j] != 'X':
			print('NO')
			sys.exit(0)
print('YES')


(n, m) = map(int, input().split())
ls = list()
dx = [0] * n
dy = [0] * m
for i in range(n):
	ls.append(input())
	for j in range(len(ls[i])):
		if ls[i][j] != '.':
			dx[i] += 1
			dy[j] += 1
ans1 = set()
ans2 = set()
for i in range(n):
	if dx[i]:
		ans1.add(dx[i])
for i in range(m):
	if dy[i]:
		ans2.add(dy[i])
if len(ans1) == 1 and len(ans2) == 1:
	print('YES')
else:
	print('NO')


(n, m) = [int(i) for i in input().split()]
flg = 0
ans = 1
chk = ''
for i in range(n):
	tmp = input()
	if flg == 0 and 'X' in tmp:
		chk = tmp
		tmp = tmp.rstrip('.').lstrip('.')
		if '.' in tmp:
			ans = 0
			break
		else:
			flg = 1
	elif flg == 1 and 'X' in tmp:
		if chk != tmp:
			ans = 0
			break
	elif flg == 1 and 'X' not in tmp:
		flg = 2
	elif flg == 2 and 'X' in tmp:
		ans = 0
		break
print('YES' if ans else 'NO')


(n, m) = map(int, input().split())
puzz = []
for _ in range(n):
	puzz.append([1 if x == 'X' else 0 for x in input()])
(hor, ver) = (set(), set())
for (i, l) in enumerate(puzz):
	for (j, quad) in enumerate(l):
		if quad:
			hor.add(i)
			ver.add(j)
ans = True
for i in hor:
	for j in ver:
		if not puzz[i][j]:
			ans = False
			break
print('YES' if ans else 'NO')


(n, m) = map(int, input().split())
piece = [input().rstrip() for i in range(n)]
(maxx, minx, maxy, miny) = (-1, n, -1, m)
count = 0
for i in range(n):
	for j in range(m):
		if piece[i][j] == 'X':
			maxx = max(maxx, i)
			minx = min(minx, i)
			maxy = max(maxy, j)
			miny = min(miny, j)
			count += 1
if (maxx - minx + 1) * (maxy - miny + 1) == count:
	print('YES')
else:
	print('NO')


import sys
(n, m) = map(int, input().split())
A = {line.rstrip() for line in sys.stdin}
print('YES' if len(A) == 1 or (len(A) == 2 and '.' * m in A) else 'NO')


(n, m) = map(int, input().split())
pzl = []
for i in range(n):
	pzl.append(list(input()))
left = m + 1
right = -1
up = n + 1
down = -1
for i in range(n):
	for j in range(m):
		if pzl[i][j] == 'X':
			if left > j:
				left = j
			if right < j:
				right = j
			if up > i:
				up = i
			if down < i:
				down = i
answ = 'YES'
for i in range(up, down + 1):
	for j in range(left, right + 1):
		if pzl[i][j] != 'X':
			answ = 'NO'
print(answ)


(n, m) = map(int, input().split())
o1 = set()
for i in range(n):
	s = input()
	if s.count('X') != 0:
		o1.add((s.count('X'), s.find('X'), s.rfind('X')))
if len(o1) == 1:
	print('YES')
else:
	print('NO')


def fail():
	print('NO')
	exit()
read = lambda : map(int, input().split())
(n, m) = read()
a = [input() for i in range(n)]
fst = None
for i in range(n):
	for j in range(m):
		if a[i][j] == 'X':
			fst = (i, j)
			break
	if fst != None:
		break
scd = None
for i in range(n - 1, -1, -1):
	for j in range(m - 1, -1, -1):
		if a[i][j] == 'X':
			scd = (i, j)
			break
	if scd != None:
		break
flag = True
for i in range(n):
	for j in range(m):
		if fst[0] <= i <= scd[0] and fst[1] <= j <= scd[1]:
			if a[i][j] == '.':
				fail()
		elif a[i][j] == 'X':
			fail()
print('YES')


(n, m) = map(int, input().split())
ss = ''
for i in range(n):
	s = str(input())
	if 'X' in s:
		if ss == '':
			ss = s
		elif s == ss:
			pass
		else:
			print('NO')
			return
print('YES')


flag = True
(r, c) = map(int, list(input().split()))
mxr = -1
mnr = r
mxc = -1
mnc = c
inp = list()
for row in range(r):
	inp.append(input())
	for col in range(c):
		if inp[row][col] == 'X':
			mxr = max(mxr, row)
			mnr = min(mnr, row)
			mxc = max(mxc, col)
			mnc = min(mnc, col)
for row in range(r):
	for col in range(c):
		if row <= mxr and row >= mnr and (col <= mxc) and (col >= mnc) and (inp[row][col] == '.'):
			flag = False
print('YES' if flag else 'NO')


(n, m) = map(int, input().split())
form = []
xs = 0
for a in range(n):
	form.append(input())
	xs += form[a].count('X')
spos = 0
for a in range(n):
	for b in range(m):
		if form[a][b] == 'X':
			spos = [a, b]
			break
	if spos != 0:
		break
x1 = 0
x2 = 0
for a in range(spos[0], n):
	if form[a][spos[1]] == 'X':
		x1 += 1
	else:
		break
for a in range(spos[1], m):
	if form[spos[0]][a] == 'X':
		x2 += 1
	else:
		break
if x1 * x2 != xs:
	print('NO')
else:
	conf = 1
	for a in range(spos[0], spos[0] + x1):
		for b in range(spos[1], spos[1] + x2):
			if form[a][b] != 'X':
				conf = 0
				break
		if conf == 0:
			break
	if conf == 0:
		print('NO')
	else:
		print('YES')


(n, m) = map(int, input().split())
a = [input() for i in range(n)]
(x1, y1, x2, y2) = (100000, 100000, -1, -1)
for i in range(n):
	for j in range(m):
		if a[i][j] == 'X':
			(x1, y1) = (min(j, x1), min(i, y1))
			(x2, y2) = (max(j, x2), max(i, y2))
f = True
for i in range(y1, y2 + 1):
	for j in range(x1, x2 + 1):
		if a[i][j] != 'X':
			f = False
if not f or ((x2 - x2) % m and (y2 - y1) % n):
	print('NO')
else:
	print('YES')


def read():
	return [int(v) for v in input().split()]

def main():
	(n, m) = read()
	s = []
	for i in range(n):
		s.append(input())
	(up, left, down, right) = (n, m, -1, -1)
	for i in range(n):
		for j in range(m):
			if s[i][j] == 'X':
				if i < up:
					up = i
				if j < left:
					left = j
				if i > down:
					down = i
				if j > right:
					right = j
	for i in range(up, down + 1):
		for j in range(left, right + 1):
			if s[i][j] != 'X':
				print('NO')
				return
	print('YES')
main()


(n, m) = list(map(int, input().split()))
pu = [input() for i in range(n)]
cors = []
res = True
for string in pu:
	if 'X' in string:
		if not len(cors):
			cors = (string.find('X'), string.rfind('X'))
		res = res and string.count('X') == cors[1] - cors[0] + 1 and (string[cors[0]:cors[1] + 1] == 'X' * (cors[1] - cors[0] + 1))
if res:
	print('YES')
else:
	print('NO')


mn = [int(x) for x in input().split()]
empty_str = '.' * mn[1]
sample = None
flag = True
for i in range(mn[0]):
	s = input()
	if s == empty_str:
		continue
	if sample is None:
		sample = s
	elif sample != s:
		flag = False
		break
print('YES' if flag else 'NO')


import sys
(n, m) = map(int, input().split())
a = [[i for i in list(input())] for j in range(n)]
b = 0
for i in range(n):
	for j in range(m):
		if a[i][j] == 'X':
			nx = j
			ny = i
			b = 1
			break
	if b:
		break
b = 0
for i in range(n - 1, -1, -1):
	for j in range(m - 1, -1, -1):
		if a[i][j] == 'X':
			dx = j
			dy = i
			b = 1
			break
	if b:
		break
b = 0
for i in range(n):
	for j in range(m):
		if i >= ny and j >= nx and (i <= dy) and (j <= dx):
			if a[i][j] != 'X' and b == 0:
				print('NO')
				b = 1
		elif a[i][j] == 'X' and b == 0:
			print('NO')
			b = 1
if b == 0:
	print('YES')


(n, m) = map(int, input().split())
l = [list(input()) for _ in range(n)]
(maxx, minx, maxy, miny) = (-1, n, -1, m)
count = 0
for i in range(n):
	for j in range(m):
		if l[i][j] == 'X':
			maxx = max(maxx, i)
			minx = min(minx, i)
			maxy = max(maxy, j)
			miny = min(miny, j)
			count += 1
if (maxx - minx + 1) * (maxy - miny + 1) == count:
	print('YES')
else:
	print('NO')


class MatrixCalculator:

	def calculate(self, x, y, rows):
		first_occurrence = True
		empty_after_x_row = False
		leftest_x = 0
		rightest_x = 0
		x_count = 0
		for row in rows:
			if 'X' in row:
				if empty_after_x_row:
					return 'NO'
				first_x = row.find('X')
				last_x = row.rfind('X')
				if first_occurrence:
					leftest_x = first_x
					rightest_x = last_x
					x_count = row.count('X')
					first_occurrence = False
				elif first_x != leftest_x or last_x != rightest_x or row.count('X') != x_count:
					return 'NO'
			elif not first_occurrence:
				empty_after_x_row = True
		return 'YES'
(x, y) = map(int, input().split())
lines = []
for i in range(0, x):
	lines.append(input())
calculator = MatrixCalculator()
print(calculator.calculate(x, y, lines))


(idx1_len, idx2_len) = (int(x) for x in input().split())
field = []
x_idx___idx1 = []
x_idx___idx2 = []
for idx1 in range(idx1_len):
	idx2___value = input()
	field.append(idx2___value)
	for (idx2, value) in enumerate(idx2___value):
		if value == 'X':
			x_idx___idx1.append(idx1)
			x_idx___idx2.append(idx2)
top_left_idx1 = min(x_idx___idx1)
top_left_idx2 = min(x_idx___idx2)
bottom_right_idx1 = max(x_idx___idx1)
bottom_right_idx2 = max(x_idx___idx2)
for idx1 in range(top_left_idx1, bottom_right_idx1 + 1):
	idx2___value = field[idx1]
	for idx2 in range(top_left_idx2, bottom_right_idx2 + 1):
		if idx2___value[idx2] != 'X':
			print('NO')
			exit()
print('YES')


(n, m) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(input()))
k = 0
min_r = n - 1
max_r = 0
min_c = m - 1
max_c = 0
for i in range(n):
	for j in range(m):
		if a[i][j] == 'X':
			k += 1
			min_r = min(min_r, i)
			max_r = max(max_r, i)
			min_c = min(min_c, j)
			max_c = max(max_c, j)
if (max_r - min_r + 1) * (max_c - min_c + 1) == k:
	print('YES')
else:
	print('NO')


(n, m) = list(map(int, input().split()))
pieces = []
s = None
f = None
flag = True
opn = False
for k in range(n):
	line = input()
	i = 0
	j = len(line) - 1
	while i < m:
		if line[i] == 'X':
			if not (s is None or i == s):
				flag = False
				break
			else:
				s = i
				break
		i += 1
	i = 0
	while i < m:
		if line[i] == 'X':
			if i != 0 and line[i - 1] == '.' and opn:
				flag = False
				break
		if line[i] == '.' and i != 0 and (line[i - 1] == 'X'):
			opn = True
		i += 1
	opn = False
	while j > -1:
		if line[j] == 'X':
			if not (f is None or j == f):
				flag = False
				break
			else:
				f = j
				break
		j -= 1
if flag:
	print('YES')
else:
	print('NO')


(n, m) = list(map(int, input().split()))
L = [str(input()) for _ in range(n)]
x = y = ok = 0
for i in range(n):
	for j in range(m):
		if L[i][j] == 'X':
			x = i
			y = j
			ok = 1
			break
	if ok:
		break
l = y
while l < m and L[x][l] == 'X':
	l += 1
ok = 0
att = 0
for i in range(x + 1, n):
	vu = 0
	for j in range(m):
		if L[i][j] == 'X':
			vu = 1
			if j < y or j >= l or att:
				ok = -1
				break
		elif vu and j >= y and (j < l):
			ok = -1
			break
		elif j >= y and j < l:
			att = 1
	if ok or vu == 0:
		break
if ok == -1:
	print('NO')
else:
	print('YES')


(n, k) = [int(i) for i in input().split()]
ans = chk = 0
for i in range(n):
	s = input()
	if chk == 0 and 'X' in s:
		j = s.rstrip('.').lstrip('.')
		if '.' in j:
			print('NO')
			exit()
		else:
			tmp = s
			chk = 1
	elif chk == 1:
		if 'X' in s and s != tmp:
			print('NO')
			exit()
		elif 'X' not in s:
			chk == 2
	elif chk == 2 and 'X' in s:
		print('NO')
		exit()
print('YES')


(n, m) = map(int, input().split())
l = []
ans = 'YES'
for i in range(n):
	l.append(input())
for x1 in range(n):
	for y1 in range(m):
		if l[x1][y1] == 'X':
			break
	if l[x1][y1] == 'X':
		break
for x2 in range(n - 1, -1, -1):
	for y2 in range(m - 1, -1, -1):
		if l[x2][y2] == 'X':
			break
	if l[x2][y2] == 'X':
		break
for i in range(x1, x2 + 1):
	for j in range(y1, y2 + 1):
		if l[i][j] == '.':
			ans = 'NO'
			break
	if ans == 'NO':
		break
if x1 > 0 and ans == 'YES':
	for i in range(y1, y2 + 1):
		if l[x1 - 1][i] == 'X':
			ans = 'NO'
if x2 < n - 1 and ans == 'YES':
	for i in range(y1, y2 + 1):
		if l[x2 + 1][i] == 'X':
			ans = 'NO'
if y1 > 0 and ans == 'YES':
	for i in range(x1, x2 + 1):
		if l[i][y1 - 1] == 'X':
			ans = 'NO'
if y2 < m - 1 and ans == 'YES':
	for i in range(x1, x2 + 1):
		if l[i][y2 + 1] == 'X':
			ans = 'NO'
print(ans)


(n, m) = list(map(int, input().split()))
s = []
for i in range(n):
	s += [input()]

def check():
	flag = False
	for i in range(n):
		for j in range(m):
			if s[i][j] == 'X':
				i1 = i
				j1 = j
				flag = True
				break
		if flag:
			break
	flag = False
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if s[i][j] == 'X':
				i2 = i
				j2 = j
				flag = True
				break
		if flag:
			break
	for i in range(n):
		for j in range(m):
			if i1 <= i <= i2 and j1 <= j <= j2:
				if s[i][j] != 'X':
					return False
			elif s[i][j] == 'X':
				return False
	return True
if check():
	print('YES')
else:
	print('NO')


(n, m) = list(map(int, input().split()))
grid = []
for _ in range(n):
	grid.append([c for c in input()])
top = n
bot = -1
left = m
right = -1
for row in range(n):
	for col in range(m):
		if grid[row][col] == 'X':
			top = min(top, row)
			bot = max(row, bot)
			left = min(col, left)
			right = max(col, right)
fail = False
for row in range(top, bot + 1):
	for col in range(left, right + 1):
		if grid[row][col] != 'X':
			fail = True
print('NO' if fail else 'YES')


(n, m) = [int(i) for i in input().split()]
field = []
for i in range(n):
	field.append(input().strip())
st_i = -1
st_j = -1
en_i = -1
en_j = -1
result = 'YES'
top_left_found = False
for i in range(n):
	for j in range(m):
		if not top_left_found and field[i][j] == 'X':
			top_left_found = True
			st_i = i
			st_j = j
			for k in range(i, n):
				if not 'X' in field[k] and en_i == -1:
					en_i = k - 1
			if en_i == -1:
				en_i = n - 1
		elif top_left_found:
			if i != st_i and en_j == -1:
				en_j = m - 1
			if field[i][j] == '.' and i == st_i and (en_j == -1):
				en_j = j - 1
			elif en_j != -1 and field[i][j] == 'X' and (j < st_j or j > en_j or i < st_i or (i > en_i)):
				result = 'NO'
			elif en_j != -1 and field[i][j] == '.' and (st_j <= j <= en_j and st_i <= i <= en_i):
				result = 'NO'
print(result)


(n, m) = list(map(int, input().split()))
x_count = 0
start_x = 0
start_y = 0
p = []
for i in range(n):
	p.append(input())
started = False
for i in range(n):
	for j in range(m):
		if p[i][j] == 'X':
			x_count += 1
		if p[i][j] == 'X' and (not started):
			started = True
			start_x = i
			start_y = j
x_len = 0
for i in range(start_x, n):
	if p[i][start_y] == 'X':
		x_len += 1
	else:
		break
y_len = 0
for i in range(start_y, m):
	if p[start_x][i] == 'X':
		y_len += 1
	else:
		break
if x_len * y_len != x_count:
	print('NO')
	return
for i in range(start_x, start_x + x_len):
	for j in range(start_y, start_y + y_len):
		if p[i][j] != 'X':
			print('NO')
			return
print('YES')


(n, m) = map(int, input().split())
a = [input() for i in range(n)]
minx = m
miny = n
maxx = -1
maxy = -1
for i in range(n):
	for j in range(m):
		if a[i][j] == 'X':
			if i > maxy:
				maxy = i
			if i < miny:
				miny = i
			if j > maxx:
				maxx = j
			if j < minx:
				minx = j
for i in range(miny, maxy + 1):
	for j in range(minx, maxx + 1):
		if a[i][j] != 'X':
			print('NO')
			break
	if a[i][j] != 'X':
		break
else:
	print('YES')


def checkrect(a, n1, n2, m1, m2):
	for i in range(n1, n2 + 1):
		for j in range(m1, m2 + 1):
			if a[i][j] != 'X':
				return False
	return True

def rect(a, n, m):
	(n1, m1, n2, m2) = (-1, -1, -1, -1)
	for i in range(n):
		if 'X' in a[i]:
			if n1 == -1:
				n1 = i
			n2 = i
	for i in range(m):
		if 'X' in [a[j][i] for j in range(n)]:
			if m1 == -1:
				m1 = i
			m2 = i
	return checkrect(a, n1, n2, m1, m2)
(n, m) = (int(z) for z in input().split())
a = []
for i in range(n):
	a.append(input())
ff = rect(a, n, m)
if ff:
	print('YES')
else:
	print('NO')


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def isRectangle():
	leftUp = [inf, inf]
	rightDown = [-1, -1]
	tot = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] == 'X':
				leftUp[0] = min(leftUp[0], i)
				leftUp[1] = min(leftUp[1], j)
				rightDown[0] = max(rightDown[0], i)
				rightDown[1] = max(rightDown[1], j)
				tot += 1
	l = abs(leftUp[0] - rightDown[0]) + 1
	r = abs(leftUp[1] - rightDown[1]) + 1
	return 'YES' if l * r == tot else 'NO'
(n, m) = value()
a = []
for i in range(n):
	a.append(input())
print(isRectangle())


(n, m) = [int(i) for i in input().split()]
pattern_dict = dict()
pattern_0 = '.' * m
no_flag = False
for i in range(n):
	s = input()
	position = [j for j in range(m) if s[j] == 'X']
	if s != pattern_0:
		if s not in pattern_dict:
			pattern_dict[s] = [i]
		else:
			pattern_dict[s].append(i)
		if len(pattern_dict) > 1 or position[-1] - position[0] + 1 != len(position):
			no_flag = True
			print('NO')
			break
if not no_flag:
	for j in pattern_dict:
		s = pattern_dict[j]
		if s[-1] - s[0] + 1 != len(s):
			print('NO')
		else:
			print('YES')


(n, m) = map(int, input().split())
g = [input() for _ in range(n)]
(r, c) = (set(), set())
for i in range(n):
	for j in range(m):
		if g[i][j] == 'X':
			r.add(i)
			c.add(j)
g = g[min(r):max(r) + 1]
g = list(map(lambda x: x[min(c):max(c) + 1], g))
good = True
for i in range(len(g)):
	for j in range(len(g[0])):
		if g[i][j] != 'X':
			good = False
			break
print('YES' if good else 'NO')


(n, m) = map(int, input().split())
osn = ' '
iter = -1
p = -1
for i in range(n):
	y = input()
	if 'X' in y and osn == ' ':
		k = y.count('X')
		f = y.index('X')
		for j in range(f, f + k):
			if y[j] != 'X':
				p = 0
		osn = y
		iter = i
	elif osn == y and osn != ' ':
		if i == iter + 1:
			iter += 1
		else:
			p = 0
	elif 'X' in y and osn != ' ':
		p = 0
if p == 0:
	print('NO')
else:
	print('YES')


(s1, e1, s2, e2) = (500, -1, 500, -1)
(n, m) = map(int, input().split())
s = set((input() for _ in range(n)))
s.discard('.' * m)
print('YES' if len(s) == 1 else 'NO')


import re
(r, c) = map(int, input().split(' '))
shape = []
for _ in range(r):
	row = input()
	if not shape:
		m = re.search('[.]*([X]+)[.]*', row)
		if m:
			sp = m.span(1)
			shape = m.group(1)
	else:
		m1 = re.search('[.]*([X]+)[.]*', row)
		if m1:
			sp1 = m1.span(1)
			if shape != m1.group(1) or sp[0] != sp1[0] or sp[1] != sp1[1]:
				print('NO')
				exit()
print('YES')


(n, m) = map(int, input().split())
board = list()
for i in range(n):
	board.append(input())
(x1, x2, y1, y2) = (n, 0, m, 0)
for i in range(n):
	for j in range(m):
		if board[i][j] == 'X':
			x1 = min(x1, i)
			x2 = max(x2, i)
			y1 = min(y1, j)
			y2 = max(y2, j)
can = True
for i in range(x1, x2 + 1):
	for j in range(y1, y2 + 1):
		if board[i][j] != 'X':
			can = False
print('YES' if can else 'NO')


(n, m) = [int(i) for i in input().split()]
p = []
for i in range(n):
	p.append(input())
fx = n + 1
fy = m + 1
lx = -1
ly = -1
for i in range(n):
	for q in range(m):
		if p[i][q] == 'X':
			fx = min(fx, i)
			lx = max(lx, i)
			fy = min(fy, q)
			ly = max(ly, q)
for i in range(fx, lx + 1):
	for q in range(fy, ly + 1):
		if p[i][q] == '.':
			print('NO')
			exit()
print('YES')


(n, m) = map(int, input().split())
puz = []
for x in range(n):
	puz.append(input())
mix = 502
miy = 502
mx = -1
my = -1
numx = 0
for i in range(n):
	for j in range(m):
		if puz[i][j] == 'X':
			miy = min(miy, i)
			my = max(my, i)
			mix = min(mix, j)
			mx = max(mx, j)
			numx = numx + 1
if (mx - mix + 1) * (my - miy + 1) == numx:
	print('YES')
else:
	print('NO')


class End:

	def __bool__(self):
		return False

def calculate(data, x, y):
	key = False
	key_first = True
	for line in data:
		if 'X' in line:
			if key == False:
				key = True
				if key_first:
					start = line.find('X')
					end = line.rfind('X')
					count = line.count('X')
			if key == End:
				return 'NO'
		else:
			if key == False:
				pass
			if key == True:
				key = End
	if key == False:
		return 'NO'
	else:
		for line in data:
			if 'X' in line:
				_start = line.find('X')
				_end = line.rfind('X')
				_count = line.count('X')
				if start != _start:
					return 'NO'
				elif end != _end:
					return 'NO'
				elif count != _count:
					return 'NO'
		return 'YES'
xy = list(map(int, input().split()))
x = xy[1]
y = xy[0]
data = list(map(str, [input() for i in range(y)]))
print(calculate(data, x, y))


(n, m) = map(int, input().strip().split())
grid = []
for i in range(n):
	grid.append(input().strip())
ul = (-1, -1)
for i in range(n):
	for j in range(m):
		if grid[i][j] == 'X':
			ul = (i, j)
			break
	if ul[0] >= 0:
		break
ll = (-1, -1)
for i in range(n - 1, -1, -1):
	for j in range(m):
		if grid[i][j] == 'X':
			ll = (i, j)
			break
	if ll[0] >= 0:
		break
ur = (-1, -1)
for i in range(n):
	for j in range(m - 1, -1, -1):
		if grid[i][j] == 'X':
			ur = (i, j)
			break
	if ur[0] >= 0:
		break
lr = (-1, -1)
for i in range(n - 1, -1, -1):
	for j in range(m - 1, -1, -1):
		if grid[i][j] == 'X':
			lr = (i, j)
			break
	if lr[0] >= 0:
		break
if ul[0] == ur[0] and ur[1] == lr[1] and (lr[0] == ll[0]) and (ll[1] == ul[1]):
	ans = True
	for i in range(ul[0], ll[0] + 1):
		for j in range(ul[1], ur[1] + 1):
			if grid[i][j] == '.':
				ans = False
				break
	if ans:
		print('YES')
	else:
		print('NO')
else:
	print('NO')


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, m) = map(int, input().split())
	arr = []
	for _ in range(n):
		arr.append(list(input()))
	(maxx, minx, maxy, miny) = (-1, n, -1, m)
	count = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] == 'X':
				maxx = max(maxx, i)
				minx = min(minx, i)
				maxy = max(maxy, j)
				miny = min(miny, j)
				count += 1
	if (maxx - minx + 1) * (maxy - miny + 1) == count:
		print('YES')
	else:
		print('NO')

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
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 nouse3():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse4():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse5():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
main()