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<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int maxn = 2e5 + 500;
bool vis[15], flag;
char str[15][15];
int marry[15];
int n, m;
bool check_c(int x, int y) {//判断这两列是否满足对称
	for (int i = 0; i < n; i++)
		if (str[marry[i]][x] != str[i][y])return false;
	return true;
}
bool check() {//在行全部随机匹配完成后进行判断是否满足通过列的随机配对得到中心对称的图像
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < m; i++)
	{
		if (vis[i])continue;
		for (int j = i + 1; j < m; j++)
			if (!vis[j] && check_c(i, j))
			{
				vis[i] = true;
				vis[j] = true;
				break;
			}
	}
	int x = -1;
	for (int i = 0; i < m; i++)
		if (!vis[i]) {
			if (m % 2 == 1 && x == -1 && check_c(i, i))
				x = i;
			else
				return false;
		}
	return true;
}
void dfs(int u) {
	if (u == n / 2) {//每次dfs随机匹配2行
		int x;
		if (n % 2 == 1) {//若是n为奇数则需要有一行自身匹配
			for (int i = 0; i < n; i++)
				if (marry[i] == -1)
					marry[i] = x = i;
		}
		if (check())
			flag = true;
		if (n % 2 == 1)marry[x] = -1;
		return;
	}
	for (int i = u; i < n; i++) {
		if (marry[i] != -1)continue;
		for (int j = i + 1; j < n; j++) {
			if (marry[j] == -1)
			{
				marry[i] = j;
				marry[j] = i;
				dfs(u + 1);
				if (flag)return;
				marry[i] = -1;//记得把之前的数据清空
				marry[j] = -1;//以便之后继续进行其他行的随机配对
			}
		}
	}
}
int main() {
	while (~scanf("%d%d", &n, &m)) {
		for (int i = 0; i < n; i++) {
			scanf("%s", &str[i]);
			marry[i] = -1;
		}
		flag = false;
		dfs(0);
		if (flag)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}