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;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H,W; cin >> H >> W;
    vector<string> S(H),T(H),U(H),V(W,""),X(W);
    for (int i=0;i<H;++i) cin >> S[i];
    for (int i=0;i<H;++i){
        T[i]=S[i]; sort(T[i].begin(),T[i].end());
    }
    int cnt=0,center=1,ok=1;
    vector<int> sym(H,-1);
    for (int i=0;i<H;++i){
        if (sym[i]>=0) continue;
        for (int j=i+1;j<H;++j){
            if (sym[j]>=0) continue;
            if (T[i]==T[j]){
                sym[j]=H-1-cnt;
                sym[i]=cnt++;
                break;
            }
        }
        if (sym[i]==-1){
            if (!center||!(H&1)) ok=0;
            else sym[i]=(H-1)/2,center=0;
        }
    }
    if (!ok){
        cout << "NO" << '\n';
        return 0;
    }
    for (int i=0;i<H;++i) U[sym[i]]=S[i];
    for (int i=0;i<W;++i){
        for (int j=0;j<H;++j) V[i]+=U[j][i];
        X[i]=V[i]; reverse(X[i].begin(),X[i].end());
    }
    center=-1; sym.assign(W,0);
    for (int i=0;i<W;++i){
        if (sym[i]) continue;
        for (int j=i+1;j<W;++j){
            if (sym[j]) continue;
            if (V[i]==X[j]){
                sym[i]=sym[j]=1;
                break;
            }
        }
        if (!sym[i]){
            if (center!=-1) ok=0;
            else center=i;
        }
    }
    if (center>=0&&V[center]!=X[center]) ok=0;
    cout << (ok?"YES":"NO") << '\n';
}