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
#include <cassert>
#include <vector>
#include <iostream>
using namespace std;

bool is_rev(string &s1, string &s2) {
    assert(s1.size() == s2.size());
    for (int i = 0, j = s2.size()-1; j >= 0; i++, j--)
        if (s1[i] != s2[j]) return false;
    return true;
}

bool check1(int H, int W, string *s, vector<int> &row_indices) {
    vector<string> cols(W, string(H, 0));
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            cols[j][i] = s[row_indices[i]][j];
    vector<bool> used(W, false);
    bool middle_used = false;
    for (int j = 0; j < W; j++) {
        if (used[j]) continue;
        for (int k = j+1; k < W; k++) {
            if (used[k]) continue;
            if (is_rev(cols[j], cols[k])) {
                used[j] = used[k] = true;
                break;
            }
        }
        if (!used[j]) {
            if (W % 2 == 0 || !is_rev(cols[j], cols[j]) || middle_used)
                return false;
            else
                middle_used = true;
        }
    }
    return true;
}

bool check(int H, int W, string *s, int a, int b) {
    vector<int> rows;
    for (int i = 0; i < H; i++)
        if ((a >> i) & 1) rows.push_back(i);
    for (int i = 0; i < H; i++)
        if ((b >> i) & 1) rows.push_back(i);
    auto l = rows.begin() + __builtin_popcount(a), r = rows.end();
    do {
        if (check1(H, W, s, rows)) return true;
    } while (next_permutation(l, r));
    return false;
}


int main() {
    int H, W; cin >> H >> W;
    string s[H]; for (int i = 0; i < H; i++) cin >> s[i];
    int ALL = (1 << H) - 1;
    for (int a = 0; a <= ALL; a++) {
        if (__builtin_popcount(a) == H/2)
            if (check(H, W, s, a, ALL^a)) { cout << "YES\n"; return 0; }
    }
    cout << "NO\n";
}
