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 <cstdio>
#include <map>
using namespace std;
typedef unsigned long long ULL;
const int N=15;
const ULL B=133333;
int n,m;
char str[N][N];
inline int abs(int x){
	return x>=0?x:-x;
}
void readData(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",str[i]+1);
}
bool use[N];
int match[N];
bool check(){
	static char a[N][N];
	int p=0;
	for(int i=1;i<=n;i++)
		if(use[i]){
			if(i<match[i]){
				p++;
				for(int j=1;j<=m;j++){
					a[p][j]=str[i][j];
					a[n-p+1][j]=str[match[i]][j];
				}
			}
		}
		else{
			for(int j=1;j<=m;j++)
				a[(n+1)>>1][j]=str[i][j];
		}
	static map<ULL,int> sum;
	static ULL f[N],b[N];
	sum.clear();
	for(int j=1;j<=m;j++){
		f[j]=b[j]=0;
		for(int i=1;i<=n;i++)
			f[j]=f[j]*B+(a[i][j]-'a'+1);
		for(int i=n;i>=1;i--)
			b[j]=b[j]*B+(a[i][j]-'a'+1);
		sum[f[j]]++;
	}
	bool useChance=(m&1)?false:true;
	for(int j=1;j<=m;j++)
		if(sum[f[j]]){
			if(f[j]==b[j]){
				int x=sum[f[j]];
				if(x&1){
					if(!useChance)
						useChance=true;
					else
						return false;
				}
				sum[f[j]]=0;
				continue;
			}
			int delta=abs(sum[f[j]]-sum[b[j]]);
			if(delta==1){
				if(!useChance)
					useChance=true;
				else
					return false;
			}
			else if(delta>1)
				return false;
			sum[f[j]]=sum[b[j]]=0;
		}
	return true;
}
bool solve(int x,bool useIdle){
	if(x==n+1)
		return check();
	if(use[x]){
		if(solve(x+1,useIdle))
			return true;
		return false;
	}
	if(!useIdle){
		use[x]=false;
		if(solve(x+1,true))
			return true;
	}
	for(int i=x+1;i<=n;i++)
		if(!use[i]){
			match[x]=i;
			match[i]=x;
			use[x]=use[i]=true;
			if(solve(x+1,useIdle))
				return true;
			use[x]=use[i]=false;
		}
	return false;
}
int main(){
	readData();
	puts(solve(1,(n&1)?false:true)?"YES":"NO");
	return 0;
}
