Milking Grid

Interview

Time limit1sMemory limit1024 MB

Summary

Given an R by C grid of letters, find the smallest-area rectangle that, repeated and cut off at the edges, rebuilds the whole grid.

Level: Medium5 of 10
Topics: String, String matching, Brute force
Solved: No attempts yet

Problem

Every morning when they are milked, Farmer John's cows form a rectangular grid that is R rows by C columns, where $1 \le R \le 10{,}000$ and $1 \le C \le 75$ . Farmer John is writing a book about cow feeding behavior. Each cow is labeled with an uppercase letter for its breed. The two-dimensional pattern of the cows during milking sometimes looks like it is built from smaller repeating rectangular patterns.

Find the rectangular unit of smallest area that can be repeated to make up the entire milking grid. The height and width of the unit do not need to divide the height and width of the grid evenly.

Input

The first line contains two space-separated integers R and C. The next R lines each contain C uppercase letters with no spaces or other characters between them. Line $i+1$ gives row $i$ of the grid.

Output

Print the area of the smallest unit from which the grid can be formed.

Hint

The entire milking grid can be constructed from repetitions of the pattern 'AB'.

Examples1

Example 1
Input
```
2 5
ABABA
ABABA
```
Expected output
```
2
```