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
def check(field):
    tr = list(map(''.join, zip(*field)))
    paired = set()
    center = -1
    for i, col1 in enumerate(tr):
        if i in paired:
            continue
        for j, col2 in enumerate(tr[i + 1:], start=i + 1):
            if j in paired:
                continue
            if col1 == col2[::-1]:
                paired.add(i)
                paired.add(j)
                break
        else:
            if center == -1 and col1 == col1[::-1]:
                center = i
            else:
                return False
    return True


def arrange_row(field, new_field, i, remain):
    if len(remain) == 0:
        return check(new_field)
    j = remain.pop()
    new_field[i] = field[j]
    for k in list(remain):
        remain.remove(k)
        new_field[h - i - 1] = field[k]
        result = arrange_row(field, new_field, i + 1, remain)
        if result:
            return True
        remain.add(k)
    remain.add(j)
    return False


def solve(h, w, field):
    new_field = [None] * h
    remaining_row = set(range(h))

    if h % 2 == 0:
        return arrange_row(field, new_field, 0, remaining_row)

    for i in list(remaining_row):
        remaining_row.remove(i)
        new_field[h // 2] = field[i]
        result = arrange_row(field, new_field, 0, remaining_row)
        if result:
            return True
        remaining_row.add(i)
    return False


h, w = map(int, input().split())
field = [input() for _ in range(h)]
print('YES' if solve(h, w, field) else 'NO')
