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<cstdio>
#define MN 12
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
char s[MN+5][MN+5];
int n,m,match[MN+5],b[MN+5],B[MN+5],ans;
bool Match(int x,int y)
{
	for(int i=1;i<=n;++i) if(s[i][x]!=s[match[i]][y]) return false;
	return true;
}
void dfs(int x,int need)
{
	if(x>n)
	{
		int flag=1,can=m&1;
		for(int i=1;i<=m;++i) B[i]=0;
		for(int i=1;i<=m;++i) if(!B[i])
		{
			int found=0;
			for(int j=i+1;j<=m;++j)
				if(!B[j]&&Match(i,j)) {B[j]=1;found=1;break;}
			if(!found) if(can)can=0; else {flag=0;break;}
		}
		if(flag) ans=1;
		return;	
	}	
	if(b[x]) return dfs(x+1,need);
	if(need) match[x]=x,dfs(x+1,0);
	for(int j=x+1;j<=n;++j) if(!b[j]) b[j]=1,match[x]=j,match[j]=x,dfs(x+1,need),b[j]=0;
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
	dfs(1,n&1);
	puts(ans?"YES":"NO");
	return 0;
}

