题目描述
Problem Background
To achieve further exploration progress, the Arecibo Telescope will capture images of Saturn's satellites. The research team must distinguish and group these satellite images, but it is not easy due to the different angles from which the satellites are photographed.
Problem Description
The captured images can be represented as an $n \times m$ matrix, where * denotes a volcano and . denotes flat land. We consider two images to belong to the same satellite if they can cyclically match by shifting up, down, left, or right.
Researchers want to find the lexicographically smallest image that belongs to the same satellite as the given image. We concatenate all rows of the image into a string and then determine the lexicographical order of the strings.
Input Format
The first line contains two integers $n, m$, representing the dimensions of the image.
The next $n$ lines, each containing $m$ characters, represent the matrix corresponding to the image.
Output Format
Output consists of $n$ lines, each containing $m$ characters, representing the lexicographically smallest image that meets the requirements.
Sample Input and Output
Sample Input #1
3 3
.**
*..
.*.
Sample Output #1
**.
..*
*..
Sample Input #2
3 4
....
..*.
....
Sample Output #2
*...
....
....
Sample Input #3
3 5
.**..
.***.
..**.
Sample Output #3
***..
.**..
**...
Notes
[Sample Explanation #1]
All possible cases:
[Data Range]
| Subtask | Score | Data Range and Constraints |
|---|---|---|
| $1$ | $10$ | $1 \le n, m \le 50$ |
| $2$ | $40$ | $1 \le n, m \le 300$ |
| $3$ | $60$ | None |
For $100\%$ of the data, $1 \le n, m \le 1000$.
[Notes]
The score for this problem is set according to the original COCI contest, with a maximum score of $110$.
This problem is translated from COCI2020-2021 CONTEST #3 T3 Sateliti.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分