Autumn Megapalindrome

Time limit1sMemory limit1024 MB

Summary

Given an n by m grid of letters, decide whether reordering rows and columns can make every row and every column a palindrome.

Level: Medium6 of 10
Topics: Math, Combinatorics, Implementation
Solved: No attempts yet

Statement

Children love playing in parks, especially when the weather is good. Today is unusually warm and sunny, so the children decided to play a very long game to keep each other busy.

For the game they prepared $nm$ square sheets of paper. Each sheet has one lowercase Latin letter written on it, and they laid the sheets out as a matrix of size $n \times m$ ( $n$ rows and $m$ columns).

Each move is one of the following two actions:

swap two columns of the matrix, keeping the order of cells within each column;
swap two rows of the matrix, keeping the order of cells within each row.

The goal is to obtain a megapalindrome, that is, a matrix in which every row and every column is a palindrome. Determine whether this is possible, or whether the game is pointless.

Input

The first line contains two integers $n$ and $m$ separated by a space, the dimensions of the matrix ( $1 \leqslant n, m \leqslant 1000$ ). The next $n$ lines each contain $m$ characters, each a lowercase Latin letter.

Output

Print the single word YES (without quotes) if the matrix can be arranged so that every row and every column is a palindrome, and NO otherwise.

Examples2

Example 1
Input
```
3 3
aar
aar
bbc
```
Expected output
```
YES
```
Example 2
Input
```
2 5
aboba
ababa
```
Expected output
```
NO
```