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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
int n, m;
char s[20][20];
int pp[20];
int match[20];
int ans = 0;
void check() {
	memset(match, 0, sizeof(match));
	int po = 0;
  	int i, j, k;
   	if(n&1){
   		for(i = 1; i <= n; i++) if(!pp[i]) po = i;
   	}
   	int res = 0;
   	if(m&1) res++;
   	for(i = 1; i <= m; i++){
   		if(match[i] > 0) continue;
    	for(j = i+1; j <= m; j++){
   			bool bk = true;
   			for(k = 1; k <= n; k++){
   				if(pp[k] > k){
   					if(s[k][i] != s[pp[k]][j] || s[pp[k]][i] != s[k][j]){ bk = false; break; }
    			}
   			}
   			if(n&1 && s[po][i] != s[po][j]) bk = false;
   			if(bk){ match[i] = j, match[j] = i; break; }
   		}
   		if(!match[i]){
   			if(res > 0) res--;
   			else return;
   		}
   	}
   	ans = 1;
}
void dfs(int x, int op) {
  	if(ans == 1) return;
   	if(x == n+1){ check(); return; }
   	if(pp[x] > 0){ dfs(x+1, op); return; }
   	for(int i = x+1; i <= n; i++){
   		if(!pp[i]){
   			pp[i] = x; pp[x] = i;
   			dfs(x+1, op);
   			pp[i] = pp[x] = 0;
   		}
   	}
   	if(n&1 && !op) dfs(x+1, 1);
}
int main() {
 	int i, j, k;
 	scanf("%d%d", &n, &m);
  	for(i = 1; i <= n; i++) scanf("%s", s[i]+1);
   	dfs(1, 0);
   	if(ans == 1) printf("YES\n");
   	else printf("NO\n");
   	return 0;
}