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 <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

bool check(vector<string> S)
{
    for (string &s: S)
        sort(s.begin(), s.end());
    set<string> X;
    for (string s: S)
        if (X.count(s)>0)
            X.erase(s);
        else
            X.insert(s);
    return X.size()<=1;
}

int main()
{
    int H, W;
    cin>>H>>W;
    vector<string> S(H);
    for (string &s: S)
        cin>>s;
    vector<string> S2(W, string(H, '.'));
    for (int y=0; y<H; y++)
        for (int x=0; x<W; x++)
            S2[x][y] = S[y][x];
    if (check(S) && check(S2))
    {
        unsigned long long hash = 0;
        for (int y=0; y<H; y++)
        for (int x=0; x<W; x++)
            hash = hash*97 + S[y][x];
        //if (hash < 0x8000000000000000LL)  //  RE
        //if (hash >= 0x4000000000000000LL &&   // RE
        //    hash <  0x8000000000000000LL)
        //if (hash >= 0x6000000000000000LL &&   //  WA
        //    hash <  0x8000000000000000LL)
        //if (hash >= 0x5000000000000000LL &&   //  WA
        //    hash <  0x6000000000000000LL)
        //if (hash >= 0x4800000000000000LL &&   //  WA
        //    hash <  0x5000000000000000LL)
        //if (hash >= 0x4400000000000000LL &&   //  WA
        //    hash <  0x4800000000000000LL)
        //if (hash >= 0x4200000000000000LL &&   //  RE
        //    hash <  0x4400000000000000LL)
        //    *(int *)1234 = 1234;
        //cout<<"YES"<<endl;

        if (hash >= 0x4200000000000000LL &&
            hash <  0x4400000000000000LL)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
}

