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;
vector<vector<pair<int,int> > > seq[13];
int main(){
	seq[0].push_back({});
	seq[2].push_back({{0, 1}});
	for(int i = 4; i <= 12; i += 2){
		for(int j = i - 1; j >= 1; j--){
			for(auto & e : seq[i - 2]){
				vector<pair<int,int> > nd;
				nd.push_back({j - 1, i - 1});
				for(auto & f : e){
					int x, y; tie(x, y) = f;
					nd.push_back({x + (x >= j - 1), y + (y >= j - 1)});
				}
				seq[i].push_back(nd);
			}
		}
	}
	int n, m;
	auto check = [&](vector<string> g){
		int hasMid = m & 1;
		vector<bool> used(m, false);
		vector<string> rev;
		for(int i = 0; i < m; i++){
			string up;
			for(int j = 0; j < n; j++) up.push_back(g[j][i]);
			rev.push_back(up);
		}
		for(int i = 0; i < m; i++){
			if(used[i]) continue;
			string c = rev[i];
			reverse(c.begin(), c.end());
			for(int j = i + 1; j < m; j++){
				if(used[j]) continue;
				if(c == rev[j]){
					used[i] = true;
					used[j] = true;
					break;
				}
			}
			if(!used[i]){
				if(c == rev[i]){
					if(hasMid){
						hasMid--;
						used[i] = true;
					} else {
						return;
					}
				} else {
					return;
				}
			}
		}
		cout << "YES" << endl;
		exit(0);
	};
	cin >> n >> m;
	vector<string> a(n), b, c;
	for(int i = 0; i < n; i++) cin >> a[i];
	int sz = n - (n&1);
	if(n & 1){
		for(int i = 0; i < n; i++){
			for(auto &e : seq[sz]){
				b = a; swap(b[i], b.back());
				c = a; c[n / 2] = b.back();
				int i = 0, j = n - 1;
				for(auto & f : e){
					c[i++] = b[f.first];
					c[j--] = b[f.second];
				}
				check(c);		
			}
		}
	} else {
		for(auto &e : seq[n]){
			c = a;
			int i = 0, j = n - 1;
			for(auto & f : e){
				c[i++] = a[f.first];
				c[j--] = a[f.second];
			}
			check(c);		
		}
	}
	cout << "NO" << endl;
	return 0;
}

