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>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_H=12,MAX_W=12;
int H,W;
string S[MAX_H],temp[MAX_H];
bool ans,rflg[MAX_H],cflg[MAX_W],cenf;
bool schk(int n,int m){
	REP(i,H){
		if (temp[i][n]!=temp[H-i-1][m]){
			return false;
		}
	}
	return true;
}
bool pal(int n){
	REP(i,H){
		if (temp[i][n]!=temp[H-i-1][n]){
			return false;
		}
	}
	return true;
}
void chk(){
	memset(cflg,false,sizeof(cflg));
	int cnt=0;
	bool cen=false;
	REP(w,W){
		if (!cflg[w]){
			cflg[w]=true;
			bool f=false;
			FOR(w2,w+1,W){
				if (!cflg[w2]){
					if (schk(w,w2)){
						cflg[w2]=true;
						cnt+=2;
						f=true;
						break;
					}
				}
			}
			if (!f){
				if (pal(w) && !cen){
					cen=true;
					cnt++;
				}
			}
		}
	}
	if (cnt==W){
		ans=true;
	}
}
void com(int n){
	if (n==H/2 && (H%2==0 || cenf)){
		chk();
	}else{
		int m=0;
		REP(i,H){
			if (!rflg[i]){
				m=i;
				break;
			}
		}
		rflg[m]=true;
		temp[n]=S[m];
		REP(i,H){
			if (!rflg[i]){
				rflg[i]=true;
				temp[H-n-1]=S[i];
				com(n+1);
				rflg[i]=false;
			}
		}
		if (!cenf && H%2){
			cenf=true;
			temp[H/2]=S[m];
			com(n);
			cenf=false;
		}
		rflg[m]=false;
	}
}
int main(){
	cin>>H>>W;
	REP(i,H){
		cin>>S[i];
	}
	REP(i,H){
		temp[i].resize(W);
	}
	com(0);
	cout<<(ans ? "YES" : "NO")<<endl;
	return 0;
}