Lexicographically Minimum Satellite Image

Given an (n \times m) matrix representing an image, where '*' denotes a volcano and '.' denotes plain land, two images are considered to belong to the same satellite if one can be obtained from the other via cyclic shifts in the vertical and/or horizontal directions. In other words, an image (B) is obtained from image (A) if there exist integers (r) and (c) such that for all (0 \le i < n) and (0 \le j < m), [ B[i][j] = A[(i+r) \bmod n][(j+c) \bmod m]. ] The lexicographical order is determined by concatenating the rows (in order) of the image into a single string. Your task is to find the lexicographically smallest image (from the equivalence class of cyclic shifts) of the given image.

inputFormat

The first line contains two integers (n) and (m). Each of the following (n) lines contains a string of length (m) consisting only of the characters '*' and '.'.

outputFormat

Output the resulting (n \times m) matrix which is the lexicographically smallest image in the same satellite. Print each of the (n) rows on a separate line.

sample

2 3
*..
..*

*..
.*.