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;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

int H,W;
string S[12];
int p[12];
bool q[12];

bool check(){
	bool b[12] = {};
	bool c = H&1;
	repp(i,0,H) if(!b[i]){
		repp(j,i+1,H) if(!b[j]){
			repp(k,0,W){
				if(S[i][p[k]] != S[j][p[W-1-k]]) break;
				if(k+1 == W) b[i] = b[j] = 1;
			}
			if(b[j]) break;
		}
		if(!b[i]){
			if(c){
				repp(k,0,W) if(S[i][p[k]] != S[i][p[W-1-k]]) return 0;
				c = 0;
			} else return 0;
		}
	}
	return 1;
}

bool solve(int a , int n , bool b){
	if(a == W) return check();
	if(q[a]) return solve(a+1,n,b);
	if(b){
		p[W/2] = a; q[a] = 1;
		if(solve(a+1,n,0)) return 1;
		q[a] = 0;
	}
	repp(i,a+1,W) if(!q[i]){
		p[n] = a; p[W-1-n] = i;
		q[a] = q[i] = 1;
		if(solve(a+1,n+1,b)) return 1;
		q[a] = q[i] = 0;
	}
	return 0;
}

int main(){
	cin >> H >> W;
	repp(i,0,H) cin >> S[i];
	cout << (solve(0,0,W&1)?"YES":"NO") << endl;
	return 0;
}
