卫星图像(Sateliti)

题目描述

为了得到进一步的探索进展，阿雷西博望远镜将拍下土星的卫星。研究团队必须区分卫星图像并将它们按卫星分组，但由于卫星从不同角度拍摄，因此并不容易。

捕捉到的图像可以以一个 $n \times m$ 的矩阵呈现，其中 * 表示火山，而 . 表示平地。我们认为两个图像属于同一颗卫星，当且仅当它们能环形地互相通过向上下或左右平移得到。

科研工作者想要找到字典序最小的与给定图像属于同一颗卫星的图像。我们把图像的所有行依次连接组成字符串，再判断字符串的字典序即可。

输入格式

第一行包含两个整数 $n,m$，表示图像的规模。

接下来的 $n$ 行，每行输入 $m$ 个字符，表示图像所对应的矩阵。

输出格式

输出共 $n$ 行，每行有 $m$ 个字符，表示满足要求的字典序最小的图像。

样例输入 #1

3 3
.**
*..
.*.

样例输出 #1

**.
..*
*..

样例输入 #2

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

样例输出 #2

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

样例输入 #3

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

样例输出 #3

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

数据范围

【样例解释 #1】

所有可能的情况：

【数据范围】

对于 $100\%$ 的数据，$1 \le n,m \le 1000$。

【说明】

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2020-2021 CONTEST #3 T3 Sateliti。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：2100。

测试点分布

出处：原题链接