题目描述

译自 COCI 2020/2021 Contest #3 T3. Sateliti

为了探查火星卫星表面的陨石坑，研究人员使用阿雷西博射电望远镜记录了其图像。他们必须辨别卫星图像，然后将其分类。由于我们可以从不同的角度拍摄卫星，这并不是一个容易的事情。

拍摄得到的图像可以用一个 $n$ 行，$m$ 列的矩阵表示。矩阵中仅有两种元素，* 和 . ，其中 * 表示陨石坑，而 . 表示平地。

我们认为两个图像表示的是同一个卫星，当且仅当其中一个图像可以通过若干次行循环移位或若干次列循环移位得到另一个图像。

给定一个图像，有许多与其表示的卫星相同的图像，你需要找到其中字典序最小的那一个。

为了得到图像之间的字典序大小关系，我们需要将图像的所有行首尾相连，然后比较连接而成的字符串得到图像之间的字典序大小关系。字符的字典序大小则通过比较其 $\texttt{ASCII}$ 码大小来得出。

输入格式

第一行包含两个整数 $n,m$ 。

接下来 $n$ 行，每行有 $m$ 个字符，表示我们得到的图像。

输出格式

输出 $n$ 行，每行输出 $m$ 行字符，即为你得到的字典序最小的图像。

样例 1

3 3
.**
*..
.*.

**.
..*
*..

所有合法的图像列举如下：

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

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

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

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

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

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

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

数据范围与提示

对于所有子任务，保证 $1 \le n,m \le 1000$ 。

详细子任务附加限制与分值如下表：