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 INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 1000007
#define INF63 1061109567
#define INF127 9187201950435737471
#define UINF 18446744073709551615
#define F first
#define S second
#define ll long long
#define N 15
#define M 5010
using namespace std;
ll n,m,cga[N],cgb[N];
string s[N],sts[N];

void dfs1(ll x,ll mr);

void dfs(ll x,ll mr)
{
	ll i;
	if(x>=n)
	{
		if(m%2==0)
		{
			dfs1(0,0);
		}
		else
		{
			dfs1(0,1);
		}
	}
	else if(cga[x]>=0)//已有匹配
	{
		dfs(x+1,mr);
	}
	else
	{
		for(i=x+1;i<n;i++)
		{
			if(cga[i]>=0||sts[i]!=sts[x])//已有匹配或不能匹配
			{
				continue;
			}
			cga[i]=x;
			cga[x]=i;
			dfs(x+1,mr);
			cga[i]=-1;
			cga[x]=-1;
		}
		if(mr==1)//单独匹配 
		{
			cga[x]=x;
			dfs(x+1,0);
			cga[x]=-1;
		}
	}
	return;
}
void dfs1(ll x,ll mr)
{
	ll i,j;
	if(x>=m)
	{
		puts("YES");
		exit(0);
	}
	else if(cgb[x]>=0)//已有匹配
	{
		dfs1(x+1,mr);
	}
	else
	{
		for(i=x+1;i<m;i++)
		{
			if(cgb[i]>=0)//已有匹配
			{
				continue;
			}
			for(j=0;j<n;j++)
			{
				if(s[j][i]!=s[cga[j]][x])//不可匹配(考虑行的可行性) 
				{
					j=-1;
					break;
				}
			}
			if(j==-1)
			{
				continue;
			}
			cgb[i]=x;
			cgb[x]=i;
			dfs1(x+1,mr);
			cgb[i]=-1;
			cgb[x]=-1;
		}
		if(mr==1)//单独匹配 
		{
			for(j=0;j<n;j++)
			{
				if(s[j][x]!=s[cga[j]][x])//不可匹配(考虑行的可行性) 
				{
					j=-1;
					break;
				}
			}
			if(j!=-1)
			{
				cgb[x]=x;
				dfs1(x+1,0);
				cgb[x]=-1;
			}
		}
	}
	return;
}
int main(){
	ll i;
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
		cin>>sts[i];
		s[i]=sts[i];
		sort(sts[i].begin(),sts[i].end());
	}
	memset(cga,-1,sizeof(cga));
	memset(cgb,-1,sizeof(cgb));
	if(n%2==0)
	{
		dfs(0,0);
	}
	else
	{
		dfs(0,1);
	}
	puts("NO");
	return 0;
}