The Smallest Wallpaper Stamp

A decorator wants to reproduce a strip of wallpaper with a single rubber stamp. The wallpaper is a list of m equal-length strings wall (n characters each). A stamp of p rows and q columns generates the wallpaper if

wall[i][j] == wall[i % p][j % q] for every row i and column j,

that is, the top-left p x q corner, repeated down and across, reproduces the whole strip. The last copies may be cut off at the bottom or right edge, so p need not divide m and q need not divide n.

Return [p, q] for the stamp with the smallest area p * q that generates wall. (The smallest-area stamp is always unique.)

Examples

Input:  wall = ["xyxyx", "zwzwz", "xyxyx", "zwzwz"]
Output: [2, 2]

Input:  wall = ["ababa", "aabaa", "ababa"]
Output: [2, 4]
Explanation: the rows repeat every 2 rows. "ababa" repeats every 2 or 4 columns
and "aabaa" every 3 or 4 columns, so both repeat every 4 columns.

Input:  wall = ["abc"]
Output: [1, 3]

Constraints

• 1 <= m, n and m * n <= 4 * 10**5
• Every string has length n and consists of lowercase letters.

Goals

• Split a two-dimensional repetition into independent row and column conditions
• Treat whole rows (or whole columns) as single symbols and find the shortest period of that sequence
• Avoid combining per-row periods with a least common multiple