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;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  auto start = clock();
  Int h,w;
  cin>>h>>w;
  vector<string> s(h);
  for(Int i=0;i<h;i++) cin>>s[i];

  auto YES=[&](){
    cout<<"YES"<<endl;
    exit(0);
  };

  auto calc=[&](string s){
    Int res=0;
    for(Int i=0;i<(Int)s.size();i++)
      res=res*26+(s[i]-'a');
    return res;
  };

  
    
  for(Int c=0;c<(w&1?w:1LL);c++){
    if(w&1){
      map<char,Int> mc;
      for(Int i=0;i<h;i++) mc[s[i][c]]++; 
      Int odd=0;
      for(auto p:mc) odd+=p.second&1;
      if(h%2==0&&odd>0) continue;
      if(h%2==1&&odd>1) continue;
    }
    Int bit=(1<<((w+1)/2))-1;
    while(bit<(1<<w)){
      //cout<<bit<<endl;
      if((w&1) && !((bit>>c)&1)){
	Int x=bit&-bit,y=bit+x;
	bit=((bit&~y)/x>>1)|y;
	continue;
      }
      
      vector<Int> x,y;
      for(Int j=0;j<w;j++){
	if((w&1) && c==j) continue;
	if((bit>>j)&1) x.emplace_back(j);
	else y.emplace_back(j);
      }      
      assert(x.size()==y.size());
      
      do{
	using P = pair<Int, Int>;
	map<P, Int> mp;
	for(Int i=0;i<h;i++){
	  string a,b;
	  for(Int j=0;j<(Int)x.size();j++){
	    a+=s[i][x[j]];
	    b+=s[i][y[j]];
	  }
	  if(w&1){
	    a+=s[i][c];
	    b+=s[i][c];
	  }
	  mp[P(calc(a),calc(b))]++;
	}	  
	auto rev=[&](P p){return P(p.second,p.first);};
	auto ch=mp;
	Int flg=1,cnt=0;
	for(auto p:mp){
	  flg&=ch[p.first]==ch[rev(p.first)];
	  cnt+=(p.first.first==p.first.second)*(p.second&1);
	}
	if(flg && ((h&1) == cnt) ) YES();
      }while(next_permutation(y.begin(),y.end()));	   

      if((double)(clock()-start)/CLOCKS_PER_SEC>1.95){
	cout<<"NO"<<endl;
	return 0;
      }
      
      {
	Int x=bit&-bit,y=bit+x;
	bit=((bit&~y)/x>>1)|y;
      }
    }
  }
  cout<<"NO"<<endl;
  return 0;
}
