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];
clock_t start;
vector< int > v;

int cmp(int a, int b) {
  for(int i = 0; i < W; i++) {
    if(S[a][v[i]] != S[b][v[W - 1 - i]]) return false;
  }
  return true;
}

bool rec() {
  vector< int > used(H);
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < i; j++) {
      if(used[j]) continue;
      if(cmp(i, j)) {
        used[i] = true;
        used[j] = true;
        break;
      }
    }
  }
  for(int i = 0; i < H; i++) {
    if(used[i]) continue;
    if(cmp(i, i)) {
      used[i] = true;
      break;
    }
  }
  return count(begin(used), end(used), 0) == 0;
}


int main() {
  start = clock();
  cin >> H >> W;
  v.resize(W);
  iota(begin(v), end(v), 0);
  for(int i = 0; i < H; i++) {
    cin >> S[i];
  }
  mt19937 mt(1333);
  while(clock() - start < 1.95 * CLOCKS_PER_SEC) {
    shuffle(begin(v), end(v), mt);
    if(rec()) {
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
}

