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 <cstdio>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 19;

char s[N][N];
int p[N];

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%s", s[i]);
  }
  for (int mask = 0; mask < (1 << n); ++mask) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (mask >> i & 1) {
        ++cnt;
      }
    }
    if (cnt != (n + 1) / 2) {
      continue;
    }
    vector<int> a, b;
    for (int i = 0; i < n; ++i) {
      if (mask >> i & 1) {
        a.push_back(i);
      } else {
        b.push_back(i);
      }
    }
    for (int i = 0; i < (n + 1) / 2; ++i) {
      p[i] = i;
    }
    do {
      map<long long, int> w;
      map<long long, long long> r;
      for (int j = 0; j < m; ++j) {
        long long x = 0;
        long long rx = 0;
        long long z = 1;
        for (int i = 0; i < n / 2; ++i) {
          x += (s[a[p[i]]][j] - 'a') * z;
          x += (s[b[i]][j] - 'a') * z * 26;
          rx += (s[b[i]][j] - 'a') * z;
          rx += (s[a[p[i]]][j] - 'a') * z * 26;
          z *= 26 * 26;
        }
        if (n % 2 == 1) {
          x += (s[a[p[n / 2]]][j] - 'a') * z;
          rx += (s[a[p[n / 2]]][j] - 'a') * z;
        }
        ++w[x];
        r[x] = rx;
      }
      bool ok = true;
      int odd = 0;
      for (auto &e : w) {
        long long rx = r[e.first];
        if (rx == e.first) {
          if (e.second % 2 == 1) {
            ++odd;
          }
        } else {
          if (w.count(rx) == 0 || w[rx] != e.second) {
            ok = false;
          }
        }
      }
      if (ok && odd == m % 2) {
        puts("YES");
        return 0;
      }
    } while (next_permutation(p, p + (n + 1) / 2));
  }
  puts("NO");
}
