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<cstdio>
#include<algorithm>
#define gc getchar()
#define N 20
#define BAS 1ll*37
#define mod 998244353
using namespace std;
inline int inn()
{
	int x,ch;while((ch=gc)<'0'||ch>'9');
	x=ch^'0';while((ch=gc)>='0'&&ch<='9')
		x=(x<<1)+(x<<3)+(ch^'0');return x;
}
int nxt[N],z[N],f[N];char s[N][N],t[N][N];
bool vis[N],chose[N],has_ans;
inline int calc_z(int x,int n)
{
	int ans=0;
	for(int i=1;i<=n;i++) ans=(ans+t[i][x]-'a'+1)*BAS%mod;
	return ans;
}
inline int calc_f(int x,int n)
{
	int ans=0;
	for(int i=n;i>=1;i--) ans=(ans+t[i][x]-'a'+1)*BAS%mod;
	return ans;
}
inline bool check(int n,int m)
{
	for(int i=1,j=0;i<=n;i++) if(nxt[i]) j++,
		memcpy(t[j],s[i],sizeof(char)*(m+1)),memcpy(t[n-j+1],s[nxt[i]],sizeof(char)*(m+1));
	if(n&1) memcpy(t[n/2+1],s[n],sizeof(char)*(m+1));
	for(int i=1;i<=m;i++) z[i]=calc_z(i,n),f[i]=calc_f(i,n);
	int res=0;memset(vis,false,sizeof(bool)*(m+1));
	for(int i=1;i<=m;i++)
		if(!vis[i]) for(int j=1;j<=m;j++) if(i^j)
			if(!vis[j]&&z[i]==f[j]) { vis[i]=vis[j]=true,res+=2;break; }
	return m-res<=1;
}
bool dfs(int n,int m,int alr,int x=1)
{
	if(n-alr<=1) return has_ans|=check(n,m);if(has_ans) return true;
	for(int i=1;i<=n/2*2;i++) if(!chose[i]) { x=i;break; }
	chose[x]=true;
	for(int i=x+1;i<=n/2*2;i++) if(!chose[i])
		nxt[x]=i,chose[i]=true,dfs(n,m,alr+2),nxt[x]=0,chose[i]=false;
	return chose[x]=false,has_ans;
}
int main()
{
	int n=inn(),m=inn();has_ans=false;
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	if(n%2==0) dfs(n,m,0);
	else for(int i=1;i<=n;i++) swap(s[i],s[n]),dfs(n,m,0),swap(s[i],s[n]);
	if(has_ans) printf("YES\n");else printf("NO\n");return 0;
}