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: interview

Starter code:

Solutions:
#!/usr/bin/env python3

def main():
    import re

    n, m = list(map(int, input().split()))
    left = right = -1
    for i in range(n):
        mt = re.search(r"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 = 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")


n, m = list(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([x[min(c): max(c) + 1] for x in 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')


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 = list(map(int, input().split()))
empthy = '.' * m
last = ''
mistake = False

for i in range(n):
    s = input()
    if s != empthy:
        if last == '':
            last = s
        else:
            if last != s:
                mistake = True
                break

if mistake:
    print('NO')
else:
    print('YES')


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')

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')


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")

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
            else:
                if s[i][j] == 'X':
                    return False
    return True

if check():
    print('YES')
else:
    print('NO')


n,m = list(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
        else:
            if dic[i][j] == '.':
                rec = False
                break
if rec:
    print("YES")
else:
    print("NO")


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")


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")

#!/usr/bin/env python3


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
            else:
                if left != cur_l:
                    print("NO")
                    return
            cur_r = line.rfind("X")
            if right is None:
                right = cur_r
            else:
                if 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())
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")
            return
        
print("YES")

# You lost the game.

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
        else:
            if 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, 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)

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")


import sys
n, m = list(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')
            return
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')
            return
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
        else:
            if s == ss:
                pass
            else:
                print("NO")
                return

print("YES")

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 = 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()))
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')


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 = list(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)


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))