For crater exploration purposes, the Arecibo telescope records images of Saturn's satellites. The scientific team must distinguish between satellite images and group the images by satellite, but it's not that simple because satellites could be shot from different angles.

Captured images can be displayed as ~n \times m~ matrices, filled with * (crater) and . (plain surface). We say that two images correspond to the same satellite if one can get the other by circular shifts of rows and columns.

To make the verification process easier, scientists want to find the lexicographically smallest image corresponding to the satellite from the given image. When comparing images, we compare strings obtained by concatenating all rows of the image, where characters are compared by ASCII value.

Input

The first line contains integers ~n~ and ~m~ ~(1 \le n, m \le 1000)~, the dimensions of the image.

Each of the following ~n~ lines contains ~m~ characters * and .. This represents the captured image.

Output

Output ~n~ lines with ~m~ characters each, the wanted lexicographically smallest image.

Scoring

Subtask	Score	Constraints
~1~	~10~	~1 \le n, m \le 50~
~2~	~40~	~1 \le n, m \le 300~
~3~	~60~	No additional constraints.

Sample Input 1

3 3
.**
*..
.*.

Sample Output 1

**.
..*
*..

Explanation for Sample Output 1

All images that can be obtained by circular shifts are:

.**    .*.    *..    **.    *..    ..*    *.*    ..*    .*.
*..    .**    .*.    ..*    **.    *..    .*.    *.*    ..*
.*.    *..    .**    *..    ..*    **.    ..*    .*.    *.*

Sample Input 2

3 4
....
..*.
....

Sample Output 2

*...
....
....

Sample Input 3

3 5
.**..
.***.
..**.

Sample Output 3

***..
.**..
**...