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>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int H,W;
string S[12];
string T[12];

bool ans;

void uku(){
    map<string,int>cnt;
    rep(j,W){
        string s;
        rep(i,H){
            if(T[i][j]=='*')s+=T[H-1-i][j];
            else s+=T[i][j];
        }
        string t=s;
        reverse(all(t));
        if(s<=t){
            cnt[s]++;
        }
        else{
            cnt[t]--;
        }
    }

    bool flag=false;
    for(auto &p:cnt){
        if(p.se==0)continue;
        string s=p.fi;
        string t=s;reverse(all(t));

        if(s!=t)return;
        if(p.se%2==0)continue;
        if(flag)return;
        flag=true;
    }
    ans=true;
}

void ei(int b,int k){
    if(b==0){
        uku();
        return;
    }

    int s=0;
    while(~b>>s&1)s++;
    T[k]=S[s];
    for(int i=s+1;i<H;i++)if(b>>i&1){
        T[H-1-k]=S[i];
        ei(b^(1<<s)^(1<<i),k+1);
    }
}

signed main(){
    cin>>H>>W;
    rep(i,H)cin>>S[i];

    if(H&1){
        S[H]=string(W,'*');
        H++;
    }
    ei((1<<H)-1,0);
    if(ans)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
