P7170 [COCI 2020/2021 #3] Satellites

To make further progress in exploration, the Arecibo telescope will take pictures of Saturn’s moons. The research team must tell the moon images apart and group them by moon, but this is not easy because the moons are photographed from different angles.

The captured image can be represented as an $n \times m$ matrix, where `*` means a volcano and `.` means flat ground. We consider two images to belong to the same moon if and only if one can be obtained from the other by **cyclically shifting (wrapping around) up/down or left/right**. The researchers want to find the **lexicographically smallest** image that belongs to the same moon as the given image. We concatenate all rows of an image in order into a single string, and compare images by the lexicographical order of these strings.

The first line contains two integers $n, m$, representing the size of the image. The next $n$ lines each contain $m$ characters, describing the matrix of the image.

Output $n$ lines, each containing $m$ characters, representing the lexicographically smallest image that satisfies the requirement.

**[Sample Explanation #1]** All possible cases:  **[Constraints]** | Subtask | Points | Constraints and Notes | | :----------: | :----------: | :----------: | | $1$ | $10$ | $1 \le n, m \le 50$ | | $2$ | $40$ | $1 \le n, m \le 300$ | | $3$ | $60$ | None | For $100\%$ of the testdata, $1 \le n, m \le 1000$. **[Notes]** **The scoring for this problem follows the original COCI problem, with a full score of $110$.** **Translated from [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _T3 Sateliti_.** Translated by ChatGPT 5