[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】** 所有可能的情况: ![](https://cdn.luogu.com.cn/upload/image_hosting/ftrlc0tx.png) **【数据范围】** | 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_。**