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;

string v[16];
bool usedc[16];
int H,W;
bool checkcols(int x,int y){
	for(int i=1;i<H;i+=2) if(v[i][x] != v[i-1][y] || v[i][y] != v[i-1][x]) return false;
	return true;
}

bool itcols(){
	int st = 0;
	while(usedc[st]) st += 1;
	usedc[st] = true;
	int left = 0;
	for(int i=st+1;i<W;i++) if(usedc[i] == false){
		left += 1;
		if(checkcols(st,i) == false) continue;
//		cout<<st+1<<" "<<i+1<<endl;
		usedc[i] = true;
		if(itcols()) return true;
		usedc[i] = false;
	}
	if(left == 0) return true;
	usedc[st] = false;
	return false;
}

bool itrows(int st){
	if(st == H-1 || st == H){
		if(itcols()) return true;
		if(W%2 == 0) return false;
		for(int i=0;i<W;i++){
			usedc[i] = true;
			if(itcols()) return true;
			usedc[i] = false;
		}
		return false;
	}
	if(itrows(st+2)) return true;
	for(int i=st+2;i<H;i++){
		swap(v[st+1],v[i]);
		if(itrows(st+2)) return true;
		swap(v[st+1],v[i]);
	}
	return false;
}


int main(){
	cin>>H>>W;
	for(int i=0;i<H;i++) cin>>v[i];
	for(int i=0;i<H;i++){
		swap(v[i],v[H-1]);
		if(itrows(0)){
			cout<<"YES"<<endl;
			return 0;
		}
		swap(v[i],v[H-1]);
	}
	cout<<"NO"<<endl;
	return 0;
}
