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<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=20+10;
const int INF=int(1e9)+10;
#define LL long long
char str[maxn][maxn];
int swaped[maxn];
bool used[maxn];
bool ans;
int n,m;
bool check() {
	memset(used,0,sizeof(used));
	for(int i=0; i<m; i++) {
		if(used[i])
			continue;
		for(int j=0; j<m; j++) {
			bool vis=true;
			if(i==j||used[j])
				continue;
			for(int k=0; k<n; k++) {
				if(str[k][i]==str[swaped[k]][j])
					continue;
				vis=false;
				break;
			}
			if(vis){
				used[i]=used[j]=true;
				break;
			}
		}
	}
	int cnt=0;
	int pos=-1;
	for(int i=0; i<m; i++)
		if(!used[i]) {
			cnt++;
			pos=i;
		}
	if(cnt>=2||(cnt&&(m%2==0)))
		return false;
	if(cnt==1) {
		for(int i=0; i<n; i++) {
			if(str[i][pos]!=str[swaped[i]][pos])
				return false;
		}
	}
	return true;
}
void dfs(int u,int falg) {
	if(u==(n+1)>>1) {
		if(check())
			ans=true;
		return ;
	}
	for(int i=u; i<n; i++) {
		if(swaped[i]==-1) {
			for(int j=i+1; j<n; j++) {
				if(swaped[j]==-1) {
					swaped[i]=j;
					swaped[j]=i;
					dfs(u+1,falg);
					swaped[i]=-1;
					swaped[j]=-1;
				}
			}
			if(falg) {
				swaped[i]=i;
				dfs(u+1,false);
				swaped[i]=-1;
			}
		}
	}
}
void init() {
	memset(swaped,-1,sizeof(swaped));
	ans=false;
}
int main() {
	while(~scanf("%d %d",&n,&m)) {
		init();
		for(int i=0; i<n; i++)
			scanf("%s",str[i]);
		if(n&1)
			dfs(0,true);
		else
			dfs(0,false);
		printf("%s\n",ans?"YES":"NO");
	}
}