Problem F: Tiled Wall

Jake was having a nice dinner with his girlfriend in one of their favorite restaurants. She was talking about feelings or something, and as it was often the case, Jake’s mind started wandering.

The wall behind her caught his attention. It was one of those old looking walls composed of tiles with different sizes and shapes. The wall was huge and he started thinking about the ammount of work that was put into building such a structure.

As he slipped deeper and deeper into his own imagination, he suddenly realized that the wall was a sham. He could see it clearly now. The wall was made out of much larger rectangular blocks, all with the same size and orientation, and each one of them was composed of several smaller tiles. The magic was gone!

Figure 1: A large wall composed of small tiles

"Were you listening to anything I said?", she asked. He nodded, as he tried to get the waiter’s attention, "Check please!". There was only one thing on his mind now: How many blocks was the wall really made of?

Figure 2: The tiles are all part of larger rectangular blocks

Task

Consider a wall that is apparently made of several small tiles. These tiles are not necessarily rectangles and can be imagined as a group of squares joined together at their edges.

A tile can only belong to one block. The wall is in fact made of larger rectangular blocks always having the same dimensions and orientation (but not necessarily the same tile patterns).

Near the wall edges, blocks can be cut into smaller pieces to fit the available space (but always maintaining the same orientation). Inner blocks, however, will always have the same size.

Given the configuration of a wall, as a grid, where a tile is defined as a collection of adjacent grid squares having the same capital letter, determine the smallest block that could be used to create the desired illusion.

Input

The first line of the input will contain two integers, W and H, representing the size of the wall. The next H lines will contain W characters from ’A’ to ’Z’ representing the wall’s configuration. If two consecutive characters (horizontally or vertically) on the grid are the same then they belong to the same tile.

Output

A line with two integers representing the width and height of the smallest block that could be used.

Constraints

1 ≤ W,H ≤ 1,200width and height of the wall

Input example 1

14 9
AABAABCEAAAEED
CDEDBDDECCDACD
ADEDAABECCBBCD
BBEBBCCCAACCEE
AAFFFFDDEBBABC
BDEBFFBCACEFFC
ADEDDDECACDDAC
BBCAABBEABBEEE
DDEBBCAACDDDAA

Output example 1

6 4

Input example 2

11 11
ABBABBBAABD
BCCBCCDEBAC
BCABDDDEBAC
ABBABABAABA
BAABDDDBDAB
BCACBBDBDAC
BDABDDDBBAD
ABCACACAACE
ACCBAAABACA
BAACDDDABAB
ACCAEEEZZYX

Output example 2

3 3

 

MIUP'2012, 20 de Outubro, DCC/FCUP

This document was translated from LATEX by HEVEA.