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
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]


# ペアのとり方は 10395 通り
# a = math.factorial(12) / (2 ** 6) / math.factorial(6)
# print(a)  # 10395

def test(groups):
    seen = [False] * 6
    order = [-1] * len(groups)
    for i, g in enumerate(groups):
        if g == -1:
            # 真ん中
            order[W // 2] = i
            continue
        if not seen[g]:
            order[g] = i
            seen[g] = True
        else:
            order[~g] = i

    # print(groups, order)
    # return False

    rows = []
    for s in S:
        row = ''
        for i in order:
            row += s[i]
        rows.append(row)
    ok = [False] * H
    for i in range(H):
        if ok[i]:
            continue
        rev = rows[i][::-1]
        for j in range(i + 1, H):
            if not ok[j] and rows[j] == rev:
                ok[i] = ok[j] = True
                break
    ng_cnt = ok.count(False)
    if ng_cnt == 0:
        return True
    if ng_cnt == 1:
        i = ok.index(False)
        return rows[i] == rows[i][::-1]
    return False


def solve(groups, depth=0):
    if depth == W // 2:
        return test(groups)

    i = 0
    for _ in range(2 if W % 2 == 1 else 1):
        while groups[i] != -1:
            i += 1

        groups[i] = depth
        for j in range(i + 1, W):
            if groups[j] != -1:
                continue
            groups[j] = depth
            if solve(groups, depth + 1):
                return True
            groups[j] = -1
        groups[i] = -1
        i += 1

    return False


groups = [-1] * W
ok = solve(groups)
if ok:
    print('YES')
else:
    print('NO')
