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

inputFormat

Input

Input is given from Standard Input in the following format:

H W S_1 S_2 : S_H

outputFormat

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

样例

3 7
atcoder
regular
contest

NO