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 main() {
	int H; int W;
	while (~scanf("%d%d", &H, &W)) {
		vector<string> S(H);
		for (int i = 0; i < H; ++ i) {
			cin >> S[i];
		}
		auto orgS = S;
		vector<string> revS;
		auto solve = [&]() {
			revS = S;
			for (auto &s : revS)
				reverse(s.begin(), s.end());
			int used = 0;
			int i = 0;
			for (int t = 0; t < H / 2; ++ t) {
				while (1) {
					for (; i < H && (used >> i & 1); ++ i);
					if (i == H) break;
					for (int k = i + 1; k < H; ++ k) if (~used >> k & 1) {
						if (S[i] == revS[k]) {
							used |= 1 << i;
							used |= 1 << k;
							goto ok;
						}
					}
					++ i;
				}
			ok:
				if (i == H) return false;
			}
			if (H % 2 == 1) {
				i = 0;
				for (; i < H && (used >> i & 1); ++ i);
				if (i == H) return false;
				return S[i] == revS[i];
			} else {
				return true;
			}
		};
		vector<bool> matched(W);
		auto swapCol = [&](int i, int j) {
			swap(matched[i], matched[j]);
			for (int k = 0; k < H; ++ k)
				swap(S[k][i], S[k][j]);
		};
		bool ans = false;
		function<void(int)> rec = [&](int i) {
			if (i == W / 2) {
				if (solve()) {
					ans = true;
				}
				return;
			}
			for (int j = 0; j < W; ++ j) if (i != j && !matched[j]) {
				matched[i] = matched[j] = true;
				swapCol(W - 1 - i, j);
				rec(i + 1);
				swapCol(W - 1 - i, j);
				matched[i] = matched[j] = false;
			}
		};
		if (W % 2 == 0) {
			rec(0);
		} else {
			for (int mid = 0; mid < W; ++ mid) {
				matched[mid] = true;
				swapCol(mid, W / 2);
				rec(0);
				swapCol(mid, W / 2);
				matched[mid] = false;
			}
		}
		puts(ans ? "YES" : "NO");
	}
}
