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>
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
int h,w;
string c[maxn],s[maxn];
int visw[maxn],vish[maxn];
void dfsw(int x,int op)
{
	if(x==w)
	{
		cout<<"YES"<<endl;
		exit(0);
	}
	else if(visw[x]!=-1)
		dfsw(x+1,op);
	else
	{
		for(int i=x+1;i<=w-1;i++)
		{
			if(visw[i]!=-1)
				continue;
			int flag=0;
			for(int j=0;j<=h-1;j++)
			{
				if(s[vish[j]][i]!=s[j][x])
				{
					flag=1;
					break;
				}
			}
			if(flag==0)
			{
				visw[x]=i;
				visw[i]=x;
				dfsw(x+1,op);
				visw[x]=-1;
				visw[i]=-1;
			}
		}
		if(op==1)
		{
			int flag=0;
			for(int j=0;j<=h-1;j++)
			{
				if(s[vish[j]][x]!=s[j][x])
				{
					flag=1;
					break;
				}
			}
			if(flag==0)
			{
				visw[x]=x;
				dfsw(x+1,0);
				visw[x]=-1;
			}
		}
	}
}
void dfsh(int x,int op)
{
	if(x==h)
	{
		int opp=w%2;
		dfsw(0,opp);
	}
	else if(vish[x]!=-1)
		dfsh(x+1,op);
	else
	{
		for(int i=x+1;i<=h-1;i++)
		{
			if(vish[i]!=-1)
				continue;
			if(c[i]!=c[x])
				continue;
			vish[x]=i;
			vish[i]=x;
			dfsh(x+1,op);
			vish[x]=-1;
			vish[i]=-1;
		}
		if(op==1)
		{
			vish[x]=x;
			dfsh(x+1,0);
			vish[x]=-1;
		}
	}
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>h>>w;
    for(int i=0;i<=h-1;i++)
	{
    	cin>>s[i];
    	c[i]=s[i];
    	sort(c[i].begin(),c[i].end());
    }
    memset(vish,-1,sizeof(vish));
    memset(visw,-1,sizeof(visw));
    int op=h%2;
    dfsh(0,op);
    cout<<"NO"<<endl;
	return 0;
}
