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;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int H,W;
string S[12];
// 点対称かどうかは，ペアの組だけ考慮すればよい
int pir[12], ok[12];

void solve(){
  fill(ok,ok+H,-1);
  rep(i,H) if(ok[i]==-1){
    rep(j,H) if(ok[j]==-1&&i!=j){
      int cnt=0;
      rep(k,W){
        if(S[i][k]!=S[j][pir[k]]) break;
        cnt++;
      }
      if(cnt==W){
        ok[i]=ok[j]=1;
        break;
      }
    }
  }
  int cnt=0, ind=-1;
  rep(i,H){
    if(ok[i]!=-1) cnt++;
    else ind=i;
  }
  if(cnt==H){
    cout<<"YES\n";
    exit(0);
  }
  if(cnt==H-1&&H%2==1){
    rep(i,W) if(S[ind][i]!=S[ind][pir[i]]) return;
    cout<<"YES\n";
    exit(0);
  }
  return;
}

void loop(int x,int flag){
  if(x==W){
    solve();
  }else if(pir[x]!=-1){
    loop(x+1,flag);
  }else{
    for(int i=x+1;i<W;i++) if(pir[i]==-1){
      pir[x]=i;
      pir[i]=x;
      loop(x+1,flag);
      pir[x]=pir[i]=-1;
    }
    if(flag){
      pir[x]=x;
      loop(x+1,0);
      pir[x]=-1;
    }
  }
  return;
}


int main(){
  cin>>H>>W;
  rep(i,H) cin>>S[i];
  fill(pir,pir+W,-1);
  int flag=(W%2==1);
  loop(0,flag);
  cout<<"NO\n";
  return 0;
}
