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 <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main()
{
    int h, w;
    cin >> h >> w;
    string s[15];
    for(int i = 0; i < h; i++) cin >> s[i];
    int c = 1;
    int l = w - 1;
    while(l > 0){
        c *= l;
        l -= 2;
    }
    for(int p = 0; p < w; p++){
        for(int q = 0; q < c; q++){
            string t[15];
            for(int i = 0; i < h; i++) t[i] = s[i];
            for(int i = 0; i < h; i++) swap(t[i][p], t[i][w / 2]);
            int m = q;
            for(int j = w - 1; j > 0; j -= 2){
                int n = m % j;
                for(int i = 0; i < h; i++) swap(t[i][(w + j - 1) / 2], t[i][(w - j + 1) / 2 + n]);
                m /= j;
            }
            bool b[15]{0};
            int d = 0;
            bool f = true;
            for(int i = 0; i < h; i++){
                if(b[i]) continue;
                reverse(t[i].begin(), t[i].end());
                bool g = false;
                for(int j = i + 1; j < h; j++){
                    if(b[j]) continue;
                    if(t[i] == t[j]){
                        g = true;
                        b[j] = true;
                        break;
                    }
                }
                if(!g){
                    if(d){
                        f = false;
                        break;
                    }
                    string u = t[i];
                    reverse(u.begin(), u.end());
                    if(u == t[i]) d++;
                    else{
                        f = false;
                        break;
                    }
                }
            }
            if(f){
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl;
}
