Note that a matrix obtained by circular shifts of rows and columns is uniquely determined by selecting the cell to be shifted to the upper left corner.

To simplify the solution, we will make a ~2n \times 2m~ matrix ~a_{i,j}~ by taking four copies of the matrix, and replacing the characters * and . with ~0~ and ~1~. We need to determine the lexicographically smallest ~n \times m~ submatrix of that matrix.

We can use two-dimensional hashing to compare submatrices: we take the hash of the element ~a_{i,j}~ to be ~a_{i,j} p^i q^j~, where ~p~ and ~q~ are distinct primes, e.g. ~2~ and ~3~. The hash of some submatrix is equal to the sum of the hashes of its elements. If we precalculate the two-dimensional prefix sums of hashes, we can efficiently get that value for any submatrix. Of course, as the numbers can get very large, we calculate the hashes modulo some large prime number, e.g. ~10^9+7~.

Two submatrices can be lexicographically compared by using binary search to find the first element in which they differ, and then comparing that element. If we first search the row, and then the column, of that element, we just need to know how to determine if some two submatrices are equal. To do that, we use the computed hash. Before we check if the hashes are equal, we need to divide (or multiply) them by appropriate powers of ~p~ and ~q~, so that powers next to corresponding elements match.

To find the lexicographically smallest ~n \times m~ submatrix, we can go through all such submatrices, and compare them with the lexicographically smallest already processed submatrix.

If at the beginning we precompute all the necessary powers of ~p~ and ~q~ in the complexity ~\mathcal O(n+m)~, the hash prefix sums can be computed in complexity ~\mathcal O(nm)~. Two submatrices can be lexicographically compared in time ~\mathcal O(\log(nm))~, so the total complexity is ~\mathcal O(nm \log(nm))~.