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 rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
bool B(int x,int i){return (x>>i)&1;}
int H,W;
string s[12];

void solve(vector<int> p){
	vector<bool> dp(1<<H);
	dp[0] = 1;

	vector<vector<bool>> ok(H,vector<bool>(H));
	rep(i,H) rep(j,H){
		bool can = 1;
		rep(k,W) if(s[i][k] != s[j][p[k]]) can = 0;
		ok[i][j] = can;
	}

	rep(b,1<<H) if(dp[b]){
		if(b==0 && H%2==1){
			rep(i,H){
				if(ok[i][i]) dp[1<<i] = 1;
			}
			continue;
		}
		rep(i,H) if(!B(b,i)){
			rep(j,i) if(!B(b,j)){
				if(ok[i][j]) dp[b|(1<<i)|(1<<j)] = 1;
			}
		}
	}
	if(dp[(1<<H)-1]){
		puts("YES");
		exit(0);
	}
}

void dfs(vector<int> p){
	vector<int> left;
	rep(i,W) if(p[i]==-1) left.pb(i);

	if((int)left.size() == W && W%2 == 1){
		rep(i,W){
			p[i] = i;
			dfs(p);
			p[i] = -1;
		}
		return;
	}
	if((int)left.size() == 0){
		solve(p);
		return;
	}
	int x = left[0];
	int K = left.size();
	rep1(i,K-1){
		int y = left[i];
		p[x] = y;
		p[y] = x;
		dfs(p);
		p[x] = p[y] = -1;
	}
}

int main(){
	cin>>H>>W;
	rep(i,H) cin>>s[i];
	vector<int> p(W,-1);
	dfs(p);
	puts("NO");
}
