p03383 AtCoder Regular Contest 095 - Symmetric Grid
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
```python
from collections import Counter
n,m = map(int,input().split())
grid = [list(input()) for i in range(n)]
def jc(a,b):
  l = len(a)
  used = [0]*l
  for i in range(l):
    if used[i]:
      continue
    for j in range(i+1,l):
      if used[j]:
        continue
      if a[i] == b[j] and b[i] == a[j]:
        used[i] = 1
        used[j] = 1
        break
  if used.count(0) <= l%2:
    return True
  else:
    return False
def judge(a):
  h = len(a)
  w = len(a[0])
  used = [0]*h
  for i in range(h):
    if used[i]:
      continue
    ci = Counter(a[i])
    for j in range(i+1,h):
      if used[j]:
        continue
      cj = Counter(a[j])
      if ci == cj:
        if jc(a[i],a[j]):
          used[i] = 1
          used[j] = 1
          break
  if used.count(0) <= h%2:
    return True
  else:
    return False
gt = list(zip(*grid))
if judge(grid) & judge(gt):
  print("YES")
else:
  print("NO")
```