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>
using namespace std;

int H, W;
string S[12];
bool U[12]; int K; int P[12];
bool R;

void check() {
  string buf(W, ' ');
  unordered_multiset<string> ss;
  for(int i = 0; i < H; ++i) {
    for(int j = 0; j < W; ++j) buf[j] = S[i][P[j]];
    ss.insert(buf);
  }
  bool failed = false;
  while(!ss.empty()) {
    auto it = ss.begin(); string s = *it; ss.erase(it);
    string r = s; reverse(r.begin(), r.end()); it = ss.find(r);
    if(it == ss.end()) {
      if(r == s && !failed) failed = true; else return;
    }
    else ss.erase(it);
  }
  R = true;
}

void go() {
  if(K == W / 2) { check(); return; }
  int s; for(s = 0; ; ++s) if(!U[s]) break;
  P[K] = s; U[s] = true;
  for(int t = 0; t < W; ++t) if(!U[t]) {
    P[W - 1 - K] = t; U[t] = true; ++K; go(); --K; U[t] = false;
  }
  U[s] = false;
}

int main() {
  cin >> H >> W;
  for(int i = 0; i < H; ++i) cin >> S[i];
  if(W % 2 == 0) go();
  else {
    for(int m = 0; m < W; ++m) {
      P[W / 2] = m; U[m] = true; go(); U[m] = false;
    }
  }
  cout << (R ? "YES" : "NO") << endl;
  return 0;
}
