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;

char buf[20][20];
bool ok[20][20];
bool done[20];
int perm[20];
bool ya[20];
int r, c;

void bf(int at)
{
	if (at == r/2)
	{
		if (r&1) for (int i = 0;i < r;i++) if (!done[i])
		{
			perm[at] = i;
			break;
		}
		for (int i = 0;i < c;i++) ya[i] = false;
		for (int i = 0;i < c;i++) if (!ya[i]) for (int j = i+1;j < c;j++) if (!ya[j])
		{
			bool yes = true;
			for (int k = 0;k < r;k++) if (buf[perm[k]][i] != buf[perm[r-k-1]][j])
			{
				yes = false;
				break;
			}
			if (yes)
			{
				ya[i] = ya[j] = true;
				break;
			}
		}
		bool has = false;
		for (int i = 0;i < c;i++) if (!ya[i])
		{
			if (has) return;
			for (int j = 0;j < r;j++) if (buf[perm[j]][i] != buf[perm[r-j-1]][i]) return;
			has = true;
		}
		printf("YES\n");
		exit(0);
	}
	for (int i = at;i < r;i++) if (!done[i])
	{
		done[i] = true;
		perm[at] = i;
		for (int j = i+1;j < r;j++) if (!done[j] && ok[i][j])
		{
			done[j] = true;
			perm[r-at-1] = j;
			bf(at+1);
			done[j] = false;
		}
		done[i] = false;
	}
}

int main()
{
	scanf("%d%d", &r, &c);
	for (int i = 0;i < r;i++) scanf("%s", buf[i]);
	for (int i = 0;i < r;i++) for (int j = i+1;j < r;j++)
	{
		string x, y;
		for (int k = 0;k < c;k++) x.push_back(buf[i][k]), y.push_back(buf[j][k]);
		sort(x.begin(), x.end());
		sort(y.begin(), y.end());
		if (x == y) ok[i][j] = true;
	}
	bf(0);
	printf("NO\n");
	return 0;
}
