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>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)

const int INF = 1e9 + 10;

int N;
int pos[2][2020];
int L[2][2020][2020];
int dp[2020][2020];

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

bool check(){
	bool b[12] = {};
	bool c = H&1;
	rep(i,H) if(!b[i]){
		for(int j = i+1; j < H; ++j) if(!b[j]){
			rep(k,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){
				rep(k,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;
    }
    for(int i = a+1; i < W; ++i) {
        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;
	rep(i,H) cin >> S[i];
	cout << (solve(0,0,W&1)?"YES":"NO") << endl;
	return 0;
}