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 <string>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
typedef pair<int, int> P;

int h, w;
string s[15];
bool used[15];
vector<P> vec;
multiset<string> S;

bool check2()
{
	multiset<string> T;
	for(auto it = S.begin(); it != S.end(); it++) T.insert(*it);
	while(T.size()){
		string p = *T.begin();
		string q = p;
		reverse(q.begin(), q.end());
		if(p == q && T.count(q) < 2) return false;
		if(p != q && T.count(q) == 0) return false;
		T.erase(T.begin());
		T.erase(T.lower_bound(q));
	}
	return true;
}

bool check()
{
	S.clear();
	string t[15];
	for(int i = 0; i < w; i++){
		for(int j = 0; j < vec.size(); j++) t[i] += s[vec[j].first][i];
		for(int j = (int)vec.size()-1; j >= 0; j--) t[i] += s[vec[j].second][i];
		S.insert(t[i]);
	}
	if(w % 2){
		for(int i = 0; i < w; i++){
			S.insert(t[i]);
			if(check2()) return true;
			S.erase(S.lower_bound(t[i]));
		}
		return false;
	}
	return check2();
}

bool dfs()
{
	int x = -1;
	for(int i = 0; i < h; i++){
		if(!used[i]){
			x = i;
			break;
		}
	}
	if(x != -1){
		for(int i = x+1; i < h; i++){
			if(used[i]) continue;
			used[x] = used[i] = true;
			vec.push_back(make_pair(x, i));
			if(dfs()) return true;
			vec.pop_back();
			used[x] = used[i] = false;
		}
		return false;
	}
	return check();
}

int main(void)
{
	cin >> h >> w;
	for(int i = 0; i < h; i++) cin >> s[i];
	
	if(h % 2){
		for(int i = 0; i < h; i++){
			vec.push_back(make_pair(i, i));
			used[i] = true;
			if(dfs()){
				cout << "YES" << endl;
				return 0;
			}
			vec.pop_back();
			used[i] = false;
		}
	}
	else{
		if(dfs()){
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
	return 0;
}