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 <stdio.h>
int f(int a){
    if(a==0||a==1||a==-1){return 1;}
    else{return a*f(a-2);}
}
int main(void){
int h,w,x,y,z,i,j,k,l,p,q,r,n,m;
n=0;
scanf("%d%d",&h,&w);
char a[h][w];
for(i=0;i<h;i++){
    scanf("%s",a[i]);
}
int b[w],c[h],d[w];
if(w%2==0)m=w-1;
if(w%2==1)m=w;
for(i=0;i<f(m);i++){
    x=i;
    for(j=0;j<w;j++){b[j]=-1;}
    for(j=0;j<(w+1)/2;j++){
        y=x/f(m-(j+1)*2);
        z=x%f(m-(j+1)*2);
        x=z;k=0;
        if(j==0&&w%2==1){b[y]=(w-1)/2;}else{
        while(b[k]!=-1){k++;}
        b[k]=j-w%2;p=0;
        while (p!=y+1){
            k++;
            if(b[k]==-1)p++;
        }
        b[k]=w-1-j+w%2;}
    }
    for(j=0;j<w;j++){
        d[b[j]]=j;
    }
   for(j=0;j<w;j++){
       b[j]=d[j];
   } 
    for(j=0;j<h;j++){c[j]=0;}
    k=0;
    for(k=0;k<h;k++){
    if(c[k]==0){
    for(l=k+1;l<h;l++){
        if(c[l]==0){
            q=0;
            for(p=0;p<w;p++){
                if(a[k][b[p]]==a[l][b[w-1-p]])q++;
            }
            if(q==w){c[k]=1;c[l]=1;l=h;}
        }
    }}}q=0;
    for(j=0;j<h;j++){
      q+=c[j];  
    }
    if(q==h-1){
        k=0;r=0;
        while(c[k]!=0){k++;}
        for(p=0;p<w;p++){
            if(a[k][b[p]]==a[k][b[w-1-p]])r++;
        }
        if(r==w)c[k]=1;
    }q=0;
    for(j=0;j<h;j++){
        q+=c[j];
    }
    if(q==h)n++;
}
if(n>0)printf("YES\n");
if(n==0)printf("NO\n");
}
