[COCI2020-2021#3] Sateliti
题目背景
为了得到进一步的探索进展，阿雷西博望远镜将拍下土星的卫星。研究团队必须区分卫星图像并将它们按卫星分组，但由于卫星从不同角度拍摄，因此并不容易。
题目描述
捕捉到的图像可以以一个 $n \times m$ 的矩阵呈现，其中 `*` 表示火山，而 `.` 表示平地。我们认为两个图像属于同一颗卫星，当且它们能**环形地互相通过向上下或左右平移得到**。
科研工作者想要找到**字典序最小**的与给定图像属于同一颗卫星的图像。我们把图像的所有行依次连接组成字符串，再判断字符串的字典序即可。
输入输出格式
输入格式
第一行包含两个整数 $n,m$，表示图像的规模。
接下来的 $n$ 行，每行输入 $m$ 个字符，表示图像所对应的矩阵。
输出格式
输出共 $n$ 行，每行有 $m$ 个字符，表示满足要求的字典序最小的图像。
输入输出样例
输入样例 #1
3 3
.**
*..
.*.输出样例 #1
**.
..*
*..输入样例 #2
3 4
....
..*.
....输出样例 #2
*...
....
....输入样例 #3
3 5
.**..
.***.
..**.输出样例 #3
***..
.**..
**...说明
**【样例解释 #1】**
所有可能的情况：
**【数据范围】**
| Subtask | 分值 | 数据范围及约定 |
| :----------: | :----------: | :----------: |
| $1$ | $10$ | $1 \le n,m \le 50$ |
| $2$ | $40$ | $1 \le n,m \le 300$ |
| $3$ | $60$ | 无 |
对于 $100\%$ 的数据，$1 \le n,m \le 1000$。
**【说明】**
**本题分值按 COCI 原题设置，满分 $110$。**
**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _T3 Sateliti_。**