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 <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
// all ways to form pairs so that p[0] paired with p[n-1], p[1] with p[n-1], ...
void paired_permutations(int n, const function<void(vector<int>& p)>& f) {
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    function<void(int)> rb = [&](int i) {
        if(i == n / 2) {
            f(p);
        } else {
            for(int j = i + 1; j < n - i; j++) {
                swap(p[j], p[n - 1 - i]);
                rb(i + 1);
                swap(p[j], p[n - 1 - i]);
            }
        }
    };
    if(n % 2) {
        for(int i = 0; i < n; i++) {
            swap(p[i], p[n / 2]);
            rb(0);
            swap(p[i], p[n / 2]);
        }
    } else {
        rb(0);
    }
}
bool is_palindrome(const string& s) {
    string t = s;
    reverse(t.begin(), t.end());
    return s == t;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int h, w;
    cin >> h >> w;
    #define H 12
    static string s[H];
    for(int i = 0; i < h; i++) {
        cin >> s[i];
    }
    bool can = false;
    paired_permutations(w, [&](vector<int>& p) {
        multiset<string> x;
        for(int i = 0; i < h; i++) {
            string cur = "";
            for(int j = 0; j < w; j++) {
                cur += s[i][p[j]];
            }
            reverse(cur.begin(), cur.end());
            if(x.count(cur)) {
                x.erase(x.find(cur));
            } else {
                reverse(cur.begin(), cur.end());
                x.insert(cur);
            }
        }
        can |= h % 2 ? x.size() == 1 and is_palindrome(*x.begin()) : x.empty();
    });
    cout << (can ? "YES" : "NO") << endl;
    return 0;
}
