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 <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	for (int i = 0; i < H; ++i) cin >> S[i];
	function<bool(vector<int>)> solve = [&](vector<int> p) {
		if (p.size() == H) {
			vector<string> verti(W);
			for (int i = 0; i < W; ++i) {
				for (int j = 0; j < H; ++j) {
					verti[i] += S[p[j]][i];
				}
			}
			int cnt = 0;
			vector<bool> used(W);
			for (int i = 0; i < W; ++i) {
				if (used[i]) continue;
				string t = verti[i];
				reverse(t.begin(), t.end());
				for (int j = 0; j < W; ++j) {
					if (i != j && verti[j] == t && !used[j]) {
						used[i] = true;
						used[j] = true;
						cnt += 2;
						break;
					}
				}
			}
			if (W - cnt == 1) {
				for (int i = 0; i < W; ++i) {
					if (!used[i]) {
						string t = verti[i];
						reverse(t.begin(), t.end());
						if (t == verti[i]) ++cnt;
					}
				}
			}
			if (W == cnt) return true;
			return false;
		}
		int M = p.size();
		vector<bool> usedp(H);
		for (int i : p) usedp[i] = true;
		for (int i = 0; i < H; ++i) {
			if (usedp[i]) continue;
			bool ok = true;
			if (M >= 1 && M < H / 2 && p[M - 1] > i) ok = false;
			if (M > H - M - 1 && p[H - M - 1] > i) ok = false;
			if (ok) {
				p.push_back(i);
				if (solve(p)) return true;
				p.pop_back();
			}
		}
		return false;
	};
	bool ans = solve(vector<int>());
	cout << (ans ? "YES" : "NO") << endl;
	return 0;
}