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<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
#define N 12
int h,w;
string c[N];

bool Rev_same(string a,string b){
    lol(i,a.size()){
	if(a[i]!=b[a.size()-1-i])return 0;
    }
    return 1;
}
bool Palindrome(string a){
    for(int i=0;i<a.size();i++){
	if(a[i]!=a[a.size()-1-i])return 0;
    }
    return 1;
}
bool Judge(int arr[]){
    //lol(i,h)cout<<arr[i]<<" ";cout<<endl;
    string m[N];
    lol(i,w)m[i]="";
    lol(i,h){
	lol(j,w)m[j].push_back(c[arr[i]][j]);
    }
    bool used[N];
    bool odd=(w%2==1);
    lol(i,w)used[i]=0;
    lol(k,w){
	if(used[k])continue;
	bool done=0;
	for(int i=k+1;i<w;i++){
	    if(Rev_same(m[k],m[i])){
		used[i]=1;
		done=1;
		break;
	    }
	}
	if(done==0){
	    if(odd==0)return 0;
	    if(Palindrome(m[k])==0)return 0;
	    odd=0;
	    used[k]=1;
	}
    }
    return 1;
}

int arr[N];
bool used[N];
bool dfs(){
    int cnt=0,first=mod;
    lol(i,h){
	cnt+=used[i];
	if(used[i]==0)first=min(i,first);
    }
    if(cnt==h){
	if(Judge(arr)==1)return 1;
	return 0;
    }
    if((h-cnt)%2==1){
	arr[h/2]=first;
	used[first]=1;
	if(dfs()==1)return 1;
	used[first]=0;
	if(h-cnt==1)return 0;
    }
    arr[cnt/2]=first;
    used[first]=1;
    for(int i=first+1;i<h;i++){
	if(used[i])continue;
	arr[h-1-cnt/2]=i;
	used[i]=1;
	if(dfs()==1)return 1;
	used[i]=0;
    }
    used[first]=0;
    return 0;
}

int main(){
    cin>>h>>w;
    lol(i,h){
	cin>>c[i];
	used[i]=0;
    }
    cout<<(dfs()?"YES":"NO")<<endl;
    return 0;
}
