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 n,m;

bool check(vector<string> &a){
	set<string> s;
	
	for(int i=0;i<m;i++){
		string cur,rev;
		for(int j=0;j<n;j++){
			rev+=a[j][i];
		}
		cur=rev;
		reverse(rev.begin(),rev.end());
		
		if(s.find(rev) == s.end()){
			s.insert(cur);
		}
		else{
			s.erase(rev);
		}
	}
	
	if(s.empty())
		return 1;
	else if(s.size()>1)
		return 0;
	else{
		auto cur = *s.begin();
		for(int j=0;j<n;j++){
			if(cur[j]!=cur[n-j-1])
				return 0;
		}
		return 1;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	
	cin >> n >> m;
	vector<string> a(n);
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	
	int runs = 100000;
	while(runs--){
		shuffle(a.begin(),a.end(),rng);
		if(check(a)){
			cout << "YES" << endl;
			return 0;
		}
	}
	
	cout << "NO" << endl;
	return 0;
}