Description

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.

Input Format

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 Format

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

3 3
.**
*..
.*.

**.
..*
*..

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

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

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

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

Hint

[Sample Explanation #1]

All possible cases:

[Constraints]

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 CONTEST #3 T3 Sateliti.

Translated by ChatGPT 5