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;

int row,col;
char s[20][20],c[22];
string f[20];
bool g_row[20][20],g_col[20][20];
int a[20];

bool dfs_col(int j,int mask)
{
	if(j==-1){return true;}
	int u=col-j-1;
	if(u==j){
		for(int k=0;k<col;k++){
			if(dfs_col(j-1,mask|(1<<k))) return true;
		}
	}
	else{
		int cnt=0;
		while(mask&(1<<cnt)) cnt++;
		mask|=1<<cnt;
		for(int k=0;k<col;k++) if((mask&(1<<k))==0&&g_col[cnt][k]){
			if(dfs_col(j-1,mask|(1<<k))) return true;
		}
	}
	return false;
}

bool dfs_row(int i,int mask)
{
    //cout<<i<<endl;
	if(i==-1){
		for(int k1=0;k1<col;k1++){
			for(int k2=0;k2<col;k2++){
				bool f=true;
				for(int k=0;k<row;k++){
					if(s[a[k]][k1]!=s[a[row-k-1]][k2]){
						f=false;
						break;
					}
				} 
				g_col[k1][k2]=f;
			}
		}
		return dfs_col((col-1)/2,0);
	}
	int u=row-i-1;
	if(u==i){
		for(int k=0;k<row;k++){
			a[i]=k;
			if(dfs_row(i-1,mask|(1<<k))) return true;
		}
	}
	else{
		int cnt=0;
		while(mask&(1<<cnt)) cnt++;
		a[i]=cnt;
		mask|=1<<cnt;
		for(int k=0;k<row;k++){
			if((mask&(1<<k))==0&&g_row[cnt][k]){
				a[u]=k;
				if(dfs_row(i-1,mask|(1<<k))) return true;
			}
		}
	}
	return false;
}

int main()
{
	cin>>row>>col;
	for(int i=0;i<row;i++) cin>>s[i];
	for(int i=0;i<row;i++){
		for(int j=0;j<col;j++){
			c[j]=s[i][j];
		}
		sort(c,c+col);
		for(int j=0;j<col;j++) f[i]+=c[j];
	}
	for(int i=0;i<row;i++) for(int j=0;j<row;j++) g_row[i][j]=(f[i]==f[j]);
	printf(dfs_row((row-1)/2,0)?"YES":"NO");
	return 0;
}