There is an H \times W grid (H vertical, W horizontal), where each square contains a lowercase English letter. Specifically, the letter in the square at the i-th row and j-th column is equal to the j-th character in the string S_i.

Snuke can apply the following operation to this grid any number of times:

* Choose two different rows and swap them. Or, choose two different columns and swap them.



Snuke wants this grid to be symmetric. That is, for any 1 \leq i \leq H and 1 \leq j \leq W, the letter in the square at the i-th row and j-th column and the letter in the square at the (H + 1 - i)-th row and (W + 1 - j)-th column should be equal.

Determine if Snuke can achieve this objective.

Constraints

* 1 \leq H \leq 12
* 1 \leq W \leq 12
* |S_i| = W
* S_i consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:


H W
S_1
S_2
:
S_H


Output

If Snuke can make the grid symmetric, print `YES`; if he cannot, print `NO`.

Examples

Input

2 3
arc
rac


Output

YES


Input

3 7
atcoder
regular
contest


Output

NO


Input

12 12
bimonigaloaf
faurwlkbleht
dexwimqxzxbb
lxdgyoifcxid
ydxiliocfdgx
nfoabgilamoi
ibxbdqmzxxwe
pqirylfrcrnf
wtehfkllbura
yfrnpflcrirq
wvcclwgiubrk
lkbrwgwuiccv


Output

YES
input = raw_input
range = xrange

n, m = map(int,input().split())
grid = [input() for i in range(n)]

use = [False]*n
cur = []
def backtrack_even(i, rem, addwhat):
    if rem == 0:
        if addwhat != None: cur.append(addwhat)
        check(cur)
        if addwhat != None: cur.pop()
        return
    if use[i]: return backtrack_even(i+1, rem, addwhat)
    use[i] = True; cur.append(i)
    for j in range(i+1, n):
        if use[j]: continue
        use[j] = True; cur.append(j)
        backtrack_even(i+1, rem-2, addwhat)
        use[j] = False; cur.pop()
    use[i] = False; cur.pop()

def backtrack():
    if n%2 == 0: return backtrack_even(0, n, None)
    for i in range(n):
        use[i] = True
        backtrack_even((0 if i else 1), n-1, i)
        use[i] = False

middle_initial = (m%2 == 0)
from collections import Counter
def check(cur):
    P = cur[::2] + cur[1::2][::-1]
    cols = Counter((''.join(grid[P[i]][j] for i in range(n))) for j in range(m))
    #print(cur, P, cols)
    middle_filled = middle_initial
    rem = m
    while rem:
        w = next(iter(cols))
        cols[w]-= 1; rem-= 1
        if cols[w] == 0: del cols[w]
        w2 = w[::-1]
        if w2 in cols:
            assert cols[w2]
            cols[w2]-= 1; rem-= 1
            if cols[w2] == 0: del cols[w2]
        elif w == w[::-1] and not middle_filled:
            middle_filled = True
        else: return False
    print("YES"); exit()

backtrack()
print("NO")